#include <bits/stdc++.h>
using namespace std;
const int N = 105, S = 101, T = 102, inf = 1 << 29;
map<int, bool> h;
struct arr {
  int y, nex, v;
} g[N * N];
int n, m, pos[N], dis[N], que[N], flow, ans, a[N], sz = 1, p[N * N], pz, d1[N],
                                                   d2[N];
void Adde(int x, int y, int z) { g[++sz] = (arr){y, pos[x], z}, pos[x] = sz; }
void Add(int x, int y, int z) { Adde(x, y, z), Adde(y, x, 0); }
bool Bfs() {
  memset(dis, -1, sizeof(dis));
  int hd = 1, tl = 0;
  dis[S] = 0, que[++tl] = S;
  while (hd <= tl) {
    int x = que[hd++];
    for (int i = pos[x]; i; i = g[i].nex) {
      int y = g[i].y;
      if (g[i].v && dis[y] == -1) que[++tl] = y, dis[y] = dis[x] + 1;
    }
  }
  if (dis[T] == -1) return 0;
  return 1;
}
int Dfs(int x, int mx) {
  if (x == T) return mx;
  for (int i = pos[x]; i; i = g[i].nex) {
    int y = g[i].y, k;
    if (g[i].v && dis[y] == dis[x] + 1 && (k = Dfs(y, min(g[i].v, mx)))) {
      g[i].v -= k;
      g[i ^ 1].v += k;
      return k;
    }
  }
  return 0;
}
void Dinic() {
  int ret = 0;
  while (Bfs()) {
    while (ret = Dfs(S, inf)) flow += ret;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    int k = a[i];
    for (int j = 2; j * j <= k; j++) {
      if (k % j == 0 && !h[j]) h[j] = 1, p[++pz] = j;
      while (k % j == 0) k /= j;
    }
    if (k != 1 && !h[k]) h[k] = 1, p[++pz] = k;
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &d1[i], &d2[i]);
    if (d1[i] % 2) swap(d1[i], d2[i]);
  }
  for (int o = 1; o <= pz; o++) {
    int pr = p[o];
    sz = 1;
    memset(pos, 0, sizeof(pos));
    for (int j = 1; j <= n; j++) {
      int k = 0, o = a[j];
      while (o % pr == 0) o /= pr, k++;
      if (j % 2 == 0 && k)
        Add(S, j, k);
      else if (k)
        Add(j, T, k);
    }
    for (int j = 1; j <= m; j++) Add(d1[j], d2[j], inf);
    flow = 0;
    Dinic();
    ans += flow;
  }
  printf("%d\n", ans);
  return 0;
}
