#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
inline void chmin(A &a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b) {
  if (a < b) a = b;
}
long long N, M;
long long A[111];
long long X[111], Y[111];
struct Dinic {
  struct edge {
    long long to, cap, rev;
    edge(long long to, long long cap, long long rev)
        : to(to), cap(cap), rev(rev) {}
  };
  static const long long INF = 1001001001;
  vector<vector<edge>> G;
  vector<long long> level, iter;
  Dinic(long long v) : G(v), level(v), iter(v) {}
  void addEdge(long long from, long long to, long long cap) {
    G[from].push_back(edge(to, cap, G[to].size()));
    G[to].push_back(edge(from, 0, G[from].size() - 1));
  }
  void bfs(long long s) {
    fill(level.begin(), level.end(), -1);
    queue<long long> que;
    level[s] = 0;
    que.push(s);
    while (que.size()) {
      long long v = que.front();
      que.pop();
      for (auto &e : G[v]) {
        if (e.cap && level[e.to] == -1) {
          level[e.to] = level[v] + 1;
          que.push(e.to);
        }
      }
    }
  }
  long long dfs(long long v, long long t, long long f) {
    if (v == t) return f;
    for (long long &i = iter[v]; i < G[v].size(); i++) {
      edge &e = G[v][i];
      if (e.cap > 0 && level[v] < level[e.to]) {
        long long d = dfs(e.to, t, min(f, e.cap));
        if (d > 0) {
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  long long maxFlow(long long s, long long t) {
    long long flow = 0;
    while (true) {
      bfs(s);
      if (level[t] < 0) return flow;
      fill(iter.begin(), iter.end(), 0);
      long long f;
      while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
  }
};
long long calc(vector<long long> a) {
  Dinic d(N + 114);
  long long src = N, snk = N + 1;
  for (long long i = 0; i < (N); i++) {
    if (i & 1) {
      d.addEdge(i, snk, a[i]);
    } else {
      d.addEdge(src, i, a[i]);
    }
  }
  for (long long i = 0; i < (M); i++) {
    d.addEdge(X[i], Y[i], Dinic::INF);
  }
  return d.maxFlow(src, snk);
}
signed main() {
  cin >> N >> M;
  for (long long i = 0; i < (N); i++) cin >> A[i];
  for (long long i = 0; i < (M); i++) {
    cin >> X[i] >> Y[i], X[i]--, Y[i]--;
    if (X[i] & 1) swap(X[i], Y[i]);
  }
  vector<long long> p;
  for (long long i = 0; i < (N); i++) {
    long long a = A[i];
    for (long long j = 2; j * j <= a; j++) {
      if (a % j == 0) {
        p.push_back(j);
        while (a % j == 0) a /= j;
      }
    }
    if (a != 1) p.push_back(a);
  }
  sort((p).begin(), (p).end());
  p.erase(unique((p).begin(), (p).end()), p.end());
  long long ans = 0;
  for (auto u : p) {
    vector<long long> a(N);
    for (long long i = 0; i < (N); i++) {
      while (A[i] % u == 0) {
        a[i]++;
        A[i] /= u;
      }
    }
    ans += calc(a);
  }
  cout << ans << endl;
  return 0;
}
