#include <bits/stdc++.h>
using namespace std;
int n, m, pn, v[1000], cnt, ljb[1000000], f[30000], q[1000000], s, t;
map<int, int> poi[10005];
struct aa {
  int go, s, next;
} a[1000000];
inline void add(int u, int v, int w) {
  a[++cnt].go = v;
  a[cnt].s = w;
  a[cnt].next = ljb[u];
  ljb[u] = cnt;
  a[++cnt].go = u;
  a[cnt].s = 0;
  a[cnt].next = ljb[v];
  ljb[v] = cnt;
}
inline bool bfs() {
  memset(f, -1, sizeof(f));
  int h = 0, r = 1;
  q[1] = s;
  f[s] = 1;
  while (h < r) {
    int now = q[++h];
    if (now == t) return 1;
    for (int i = ljb[now]; i; i = a[i].next) {
      int go = a[i].go;
      if (f[go] == -1 && a[i].s) {
        f[go] = f[now] + 1;
        q[++r] = go;
      }
    }
  }
  return 0;
}
int minn(int a, int b) {
  if (a < b)
    return a;
  else
    return b;
}
int dinic(int sta, int sum) {
  if (sta == t) return sum;
  int os = sum;
  for (int i = ljb[sta]; i && os; i = a[i].next) {
    int go = a[i].go;
    if (f[go] == f[sta] + 1 && a[i].s) {
      int min = dinic(go, minn(os, a[i].s));
      a[i].s -= min;
      a[i ^ 1].s += min;
      os -= min;
    }
  }
  if (os == sum) f[sta] = -1;
  return sum - os;
}
int main() {
  cnt = 1, s = 10000, t = 10001;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int td;
    scanf("%d", &td);
    v[i] = td;
    for (int ii = 2; ii * ii <= td; ii++)
      if (td % ii == 0) {
        pn++;
        poi[i][ii] = pn;
        int sum = 0;
        while (td % ii == 0) td /= ii, sum++;
        if (i & 1)
          add(s, pn, sum);
        else
          add(pn, t, sum);
      }
    if (td > 1) {
      pn++;
      poi[i][td] = pn;
      if (i & 1)
        add(s, pn, 1);
      else
        add(pn, t, 1);
    }
  }
  for (int i = 1; i <= m; i++) {
    int aa, bb;
    scanf("%d%d", &aa, &bb);
    int td = v[aa];
    for (int ii = 2; ii * ii <= td; ii++)
      if (td % ii == 0) {
        while (td % ii == 0) td /= ii;
        if (v[bb] % ii == 0) {
          if (aa & 1)
            add(poi[aa][ii], poi[bb][ii], 2000000000);
          else
            add(poi[bb][ii], poi[aa][ii], 2000000000);
        }
      }
    if (td > 1) {
      if (v[bb] % td == 0) {
        if (aa & 1)
          add(poi[aa][td], poi[bb][td], 2000000000);
        else
          add(poi[bb][td], poi[aa][td], 2000000000);
      }
    }
  }
  int ans = 0;
  while (bfs()) ans += dinic(s, 2000000000);
  printf("%d", ans);
}
