#include <bits/stdc++.h>
using namespace std;
const int maxL = 70;
int mod = 1e9 + 7;
long long mod1 = 1e9 + 7;
const int inf = 1.2e18;
const int maxn = 2e3 + 100;
const int baze = 330;
const int base = 3;
int n, m, ar[maxn], u[maxn], v[maxn];
int from[maxn];
int to[maxn];
int eof = 0;
int dis[maxn];
int source = maxn - 2;
int sink = maxn - 3;
int backup[maxn];
int w[maxn];
int head[maxn];
int chiz[maxn];
int sdfghbdf[maxn];
void add_edge(int u, int v, int W, int WW = 0) {
  from[eof] = u, to[eof] = v, w[eof] = W, sdfghbdf[eof] = head[u],
  head[u] = eof++;
  swap(u, v);
  from[eof] = u, to[eof] = v, w[eof] = WW, sdfghbdf[eof] = head[u],
  head[u] = eof++;
}
bool bfs() {
  int st = 0, en = 1;
  chiz[0] = source;
  memset(dis, 63, sizeof dis);
  dis[source] = 0;
  while (st < en) {
    int v = chiz[st++];
    for (int e = head[v]; ~e; e = sdfghbdf[e])
      if (w[e] && dis[to[e]] > dis[v] + 1) {
        dis[to[e]] = dis[v] + 1;
        chiz[en++] = to[e];
        if (to[e] == sink) return true;
      }
  }
  return false;
}
int dfs(int v, int mn = 1e9) {
  if ((v == sink) || (!mn)) return mn;
  int ret = 0;
  for (int &e = head[v]; ~e; e = sdfghbdf[e])
    if (dis[to[e]] == dis[v] + 1) {
      int x = dfs(to[e], min(mn, w[e]));
      mn -= x;
      ret += x;
      w[e] -= x;
      w[e ^ 1] += x;
      if (mn == 0) break;
    }
  return ret;
}
int flow() {
  memcpy(backup, head, sizeof head);
  int ans = 0;
  while (bfs()) {
    ans += dfs(source);
    memcpy(head, backup, sizeof head);
  }
  return ans;
}
int32_t main() {
  memset(head, -1, sizeof head);
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> ar[i];
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i], u[i]--, v[i]--;
    if (u[i] & 1) swap(u[i], v[i]);
    add_edge(u[i], v[i], 1000, 0);
  }
  int hlp = eof;
  for (int i = 0; i < n; i++)
    if (i & 1)
      add_edge(source, i, 1);
    else
      add_edge(i, sink, 1);
  vector<int> prime;
  for (int i = 0, x = ar[i]; i < n; i++, x = ar[i]) {
    for (int j = 2; j * j <= x; j++)
      while (x % j == 0) prime.push_back(j), x /= j;
    if (x > 1) prime.push_back(x);
  }
  sort((prime).begin(), (prime).end());
  prime.resize(unique((prime).begin(), (prime).end()) - prime.begin());
  int ans = 0;
  for (int x : prime) {
    for (int i = 0; i < hlp; i++) w[i] = 1000 * (i & 1);
    for (int i = 0; i < n; i++) {
      int nmdnm = ar[i];
      w[hlp + 2 * i] = 0, w[hlp + 2 * i + 1] = 0;
      while (nmdnm % x == 0) w[hlp + 2 * i]++, nmdnm /= x;
    }
    if (x == -1) {
      for (int i = 0; i < eof; i++)
        cout << from[i] << ' ' << to[i] << ' ' << w[i] << endl;
    }
    ans += flow();
    if (x == -1) {
      for (int i = 0; i < eof; i++)
        cout << from[i] << ' ' << to[i] << ' ' << w[i] << endl;
    }
  }
  cout << ans << endl;
}
