#include <bits/stdc++.h>
using namespace std;
int match[4001], d[4001];
int a[10001];
int c[4001][4001];
int tim, n, m, w[4001];
int prm[100005], tot, pr[100001];
int st[10001], ed[10001], id;
int x, y, ans, wk1[10001], b1, wk2[10001], b2;
int can(int t) {
  for (int i = 1; i <= b2; i++) {
    if (w[wk2[i]] == tim || c[t][wk2[i]] != 1) continue;
    w[wk2[i]] = tim;
    if (match[wk2[i]] == 0 || can(match[wk2[i]]) == 1) {
      match[wk2[i]] = t;
      return 1;
    }
  }
  return 0;
}
int maxmatch() {
  int ret = 0;
  for (int i = 1; i <= n; i = i + 2) {
    for (int j = st[i]; j <= ed[i]; j++) {
      b1++;
      wk1[b1] = j;
    }
  }
  for (int i = 2; i <= n; i = i + 2) {
    for (int j = st[i]; j <= ed[i]; j++) {
      b2++;
      wk2[b2] = j;
    }
  }
  for (int i = 1; i <= b1; i++) {
    tim++;
    if (can(wk1[i])) ret++;
  }
  return ret;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 2; i <= 100000; i++) {
    if (prm[i] == 0) {
      tot++;
      pr[tot] = i;
    }
    for (int j = 1; j <= tot; j++) {
      if (i * pr[j] > 100000) break;
      prm[i * pr[j]] = 1;
      if (i % pr[j] == 0) break;
    }
  }
  id = 1;
  for (int i = 1; i <= n; i++) {
    st[i] = id;
    for (int j = 1; j <= tot; j++) {
      while (a[i] % pr[j] == 0) {
        a[i] = a[i] / pr[j];
        d[id] = pr[j];
        id++;
      }
    }
    if (a[i] > 1) {
      d[id] = a[i];
      id++;
    }
    ed[i] = id - 1;
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &x, &y);
    for (int j = st[x]; j <= ed[x]; j++) {
      for (int k = st[y]; k <= ed[y]; k++) {
        if (d[j] == d[k]) {
          c[j][k] = 1;
          c[k][j] = 1;
        }
      }
    }
  }
  ans = maxmatch();
  printf("%d\n", ans);
  return 0;
}
