#include <bits/stdc++.h>
using namespace std;
bool debug = 1;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
long long ln, lk, lm;
int a[105];
vector<int> vp[105];
void pd(int x, vector<int> &p) {
  for (long long d = 2; d * d <= x; d++)
    while (x % d == 0) {
      x /= d;
      p.push_back((int)d);
    }
  if (x > 1) p.push_back(x);
}
const int maxn = 3005;
int edge[maxn][maxn];
int vis[maxn];
int cx[maxn], cy[maxn];
int nx = 3000, ny = 3000;
int line(int u) {
  int v;
  for (v = 0; v < ny; v++) {
    if (edge[u][v] && !vis[v]) {
      vis[v] = 1;
      if (cy[v] == -1 || line(cy[v])) {
        cx[u] = v;
        cy[v] = u;
        return 1;
      }
    }
  }
  return 0;
}
int maxmatch() {
  int sum = 0, i;
  memset(cx, 0xff, sizeof(cx));
  memset(cy, 0xff, sizeof(cy));
  for (i = 0; i <= nx; i++) {
    if (cx[i] == -1) {
      memset(vis, 0, sizeof(vis));
      sum += line(i);
    }
  }
  return sum;
}
int st[2][105];
int gid(int i) { return i % 2 == 0 ? (i - 2) / 2 : (i - 1) / 2; }
int main() {
  scanf("%d%d", &n, &m);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    scanf("%d", a + i);
    pd(a[i], vp[i]);
    if (i > 1)
      st[i % 2][gid(i)] = st[i % 2][gid(i) - 1] + (int)vp[i - 2].size();
  }
  for (int u, v, i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    if (u % 2 == 0) swap(u, v);
    int su = st[1][gid(u)], sv = st[0][gid(v)];
    for (int(j) = 0; (j) < (int)(vp[u].size()); (j)++) {
      int idu = su + j;
      for (int(k) = 0; (k) < (int)(vp[v].size()); (k)++)
        if (vp[u][j] == vp[v][k]) {
          int idv = sv + k;
          edge[idu][idv] = 1;
        }
    }
  }
  printf("%d\n", maxmatch());
  return 0;
}
