#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e6 + 10;
const int M = 110;
const int inf = (int)1e6;
int n, m, s, t, indx;
int cnt, prim[N], ok[N];
int a[M], p[M][40], len[M], st[M], d[M][40];
int ccnt = 1, lst[N], to[N], nxt[N], f[N];
void add(int u, int v, int ff) {
  nxt[++ccnt] = lst[u];
  lst[u] = ccnt;
  to[ccnt] = v;
  f[ccnt] = ff;
  nxt[++ccnt] = lst[v];
  lst[v] = ccnt;
  to[ccnt] = u;
  f[ccnt] = 0;
}
int head, tail, q[N], dis[N];
int bfs() {
  head = 0;
  q[tail = 1] = s;
  for (int i = 1; i <= indx; i++) dis[i] = 0;
  dis[s] = 1;
  while (head < tail) {
    int u = q[++head];
    for (int j = lst[u]; j; j = nxt[j]) {
      int v = to[j];
      if (dis[v] || !f[j]) continue;
      dis[v] = dis[u] + 1;
      q[++tail] = v;
      if (v == t) return 1;
    }
  }
  return 0;
}
int dfs(int u, int flow) {
  if (u == t) return flow;
  int ret = 0, a;
  for (int j = lst[u]; j; j = nxt[j]) {
    int v = to[j];
    if (dis[v] != dis[u] + 1) continue;
    if ((a = dfs(v, min(flow, f[j])))) {
      flow -= a;
      f[j] -= a;
      ret += a;
      f[j ^ 1] += a;
    }
  }
  return ret;
}
int main() {
  for (int i = 2; i < N; i++) {
    if (!ok[i]) prim[++cnt] = i;
    for (int j = 1; j <= cnt; j++) {
      if ((long long)prim[j] * i > N) break;
      ok[i * prim[j]] = 1;
      if (i % prim[j] == 0) break;
    }
  }
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  s = ++indx, t = ++indx;
  for (int i = 1; i <= n; i++) {
    int tmp = a[i];
    st[i] = indx;
    for (int j = 1; j <= cnt && tmp != 1; j++)
      if (tmp % prim[j] == 0) {
        p[i][++len[i]] = prim[j];
        ++indx;
        while (tmp % prim[j] == 0) tmp /= prim[j], d[i][len[i]]++;
        if (i % 2 == 1)
          add(s, indx, d[i][len[i]]);
        else
          add(indx, t, d[i][len[i]]);
      }
    if (tmp != 1) {
      p[i][++len[i]] = tmp;
      ++indx;
      d[i][len[i]] = 1;
      if (i % 2 == 1)
        add(s, indx, d[i][len[i]]);
      else
        add(indx, t, d[i][len[i]]);
    }
  }
  while (m--) {
    int i, j;
    scanf("%d %d", &i, &j);
    if (i % 2 == 0) swap(i, j);
    for (int k = 1; k <= len[i]; k++)
      for (int h = 1; h <= len[j]; h++)
        if (p[i][k] == p[j][h]) {
          add(st[i] + k, st[j] + h, inf);
        }
  }
  int ans = 0;
  while (bfs()) ans += dfs(s, inf);
  printf("%d", ans);
  return 0;
}
