#include <bits/stdc++.h>
using namespace std;
vector<int> g[3200];
bool v[3200];
int a[32000], p[32000], pnum, i, j, s[110], sa, n, m, x, y, l[3200];
bool find(int d) {
  int xx, yy;
  if (v[d]) return 0;
  v[d] = 1;
  for (xx = 0; xx < g[d].size(); xx++)
    if (!l[yy = g[d][xx]] || find(l[yy])) {
      l[yy] = d;
      return 1;
    }
  return 0;
}
int main() {
  memset(a, 0, sizeof(a));
  for (i = 4; i < 32000; i += 2) a[i] = 1;
  for (i = 3; i < 32000; i += 2)
    for (j = i * i; j < 32000; j += i) a[j] = 1;
  pnum = 0;
  for (i = 2; i < 32000; i++)
    if (a[i] == 0) p[pnum++] = i;
  cin >> n >> m;
  s[0] = 1;
  sa = 1;
  for (i = 1; i <= n; i++) {
    scanf("%d", &x);
    s[i] = s[i - 1];
    for (j = 0; (j < pnum && p[j] * p[j] <= x); j++)
      while (x % p[j] == 0) {
        x /= p[j];
        a[sa++] = p[j];
      }
    if (x > 1) a[sa++] = x;
    s[i] = sa;
  }
  for (; m; m--) {
    scanf("%d%d", &x, &y);
    for (i = s[x - 1]; i < s[x]; i++)
      for (j = s[y - 1]; j < s[y]; j++)
        if (a[i] == a[j]) {
          g[i].push_back(j);
          g[j].push_back(i);
        }
  }
  memset(l, 0, sizeof(l));
  m = 0;
  for (i = 1; i <= n; i += 2)
    for (j = s[i - 1]; j < s[i]; j++) {
      memset(v, 0, sizeof(v));
      if (find(j)) m++;
    }
  cout << m << endl;
  return 0;
}
