#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
int n, m, a[110], S, T;
int f[110][11], id[110][11], num[110][11], totid = 0;
int first[1010] = {0}, tot = 1;
int h, t, q[1010], lvl[1010], cur[1010];
struct edge {
  int v, next, f;
} e[20010];
void findfactor(int x) {
  f[x][0] = 0;
  int now = a[x];
  for (int i = 2; i <= 40000; i++)
    if (now % i == 0) {
      f[x][++f[x][0]] = i;
      id[x][f[x][0]] = ++totid;
      num[x][f[x][0]] = 0;
      while (now % i == 0) now /= i, num[x][f[x][0]]++;
    }
  if (now) {
    f[x][++f[x][0]] = now;
    id[x][f[x][0]] = ++totid;
    num[x][f[x][0]] = 1;
  }
}
void insert(int a, int b, int f) {
  e[++tot].v = b, e[tot].next = first[a], e[tot].f = f, first[a] = tot;
  e[++tot].v = a, e[tot].next = first[b], e[tot].f = 0, first[b] = tot;
}
void init() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    findfactor(i);
  }
  S = totid + 1, T = totid + 2;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= f[i][0]; j++) {
      if (i % 2)
        insert(S, id[i][j], num[i][j]);
      else
        insert(id[i][j], T, num[i][j]);
    }
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (b % 2) swap(a, b);
    int tmp1 = 1, tmp2 = 1;
    while (tmp1 <= f[a][0] && tmp2 <= f[b][0]) {
      if (f[a][tmp1] == f[b][tmp2]) {
        insert(id[a][tmp1], id[b][tmp2], inf);
        tmp1++;
      } else if (f[a][tmp1] < f[b][tmp2])
        tmp1++;
      else
        tmp2++;
    }
  }
}
bool makelevel() {
  for (int i = 1; i <= T; i++) lvl[i] = -1, cur[i] = first[i];
  h = t = 1;
  q[1] = S;
  lvl[S] = 0;
  while (h <= t) {
    int v = q[h++];
    for (int i = first[v]; i; i = e[i].next)
      if (e[i].f && lvl[e[i].v] == -1) {
        lvl[e[i].v] = lvl[v] + 1;
        q[++t] = e[i].v;
      }
  }
  return lvl[T] != -1;
}
int maxflow(int v, int maxf) {
  int ret = 0, f;
  if (v == T) return maxf;
  for (int i = cur[v]; i; i = e[i].next) {
    if (e[i].f && lvl[e[i].v] == lvl[v] + 1) {
      f = maxflow(e[i].v, min(maxf - ret, e[i].f));
      ret += f;
      e[i].f -= f;
      e[i ^ 1].f += f;
      if (ret == maxf) break;
    }
    cur[v] = i;
  }
  if (!ret) lvl[v] = -1;
  return ret;
}
void dinic() {
  int maxf = 0;
  while (makelevel()) maxf += maxflow(S, inf);
  printf("%d", maxf);
}
int main() {
  init();
  dinic();
  return 0;
}
