#include <bits/stdc++.h>
using namespace std;
int n, m;
int t;
int g[115][115];
int g2[115][115];
int d[115];
int a[105];
map<int, vector<pair<int, int>>> mp;
bool isprime[20005];
queue<pair<int, int>> Q;
int dfs(int x, int dep, int m, int p) {
  if (x == t) {
    return m;
  } else {
    for (int i = 0; i <= t; i++) {
      if (i == p) continue;
      if (g[x][i] == 0) continue;
      if (d[i] <= dep) continue;
      int tmp = dfs(i, dep + 1, min(m, g[x][i]), x);
      if (tmp) {
        g[x][i] -= tmp;
        g[i][x] += tmp;
        return tmp;
      }
    }
  }
  return 0;
}
int dinic() {
  memset(d, 0, sizeof(d));
  int ret = 0;
  while (true) {
    while (!Q.empty()) Q.pop();
    Q.push(make_pair(0, 0));
    memset(d, -1, sizeof(d));
    while (!Q.empty()) {
      int x = Q.front().first;
      int dep = Q.front().second;
      Q.pop();
      if (d[x] != -1) continue;
      d[x] = dep;
      for (int i = 0; i <= t; i++) {
        if (g[x][i] == 0) continue;
        if (d[i] == -1) {
          Q.push(make_pair(i, dep + 1));
        }
      }
    }
    if (d[t] == -1) break;
    int tmp = dfs(0, 0, 1000000007, -1);
    if (!tmp) break;
    ret += tmp;
  }
  return ret;
}
void printG() {
  for (int i = 0; i <= t; i++) {
    for (int j = 0; j <= t; j++) {
      if (g[i][j] == 0) continue;
      cerr << i << "->" << j << "=" << g[i][j] << endl;
    }
  }
  cerr << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  scanf("%d%d", &n, &m);
  t = n + 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (x & 1) {
      g2[x][y] = 1000000007;
    } else {
      g2[y][x] = 1000000007;
    }
  }
  for (int i = 1; i <= n; i++) {
    int tmp = a[i];
    for (int j = 2; j * j <= tmp; j++) {
      if (tmp % j) continue;
      if (mp.find(j) == mp.end()) {
        mp[j] = vector<pair<int, int>>();
      }
      int cnt = 0;
      while (tmp % j == 0) {
        tmp /= j;
        cnt++;
      }
      mp[j].push_back(make_pair(i, cnt));
    }
    if (tmp != 1) {
      if (mp.find(tmp) == mp.end()) {
        mp[tmp] = vector<pair<int, int>>();
      }
      mp[tmp].push_back(make_pair(i, 1));
    }
  }
  int ans = 0;
  for (map<int, vector<pair<int, int>>>::iterator it = mp.begin();
       it != mp.end(); it++) {
    vector<pair<int, int>> v = it->second;
    int x = it->first;
    memcpy(g, g2, sizeof(g));
    for (int j = 0; j < v.size(); j++) {
      int y = v[j].first;
      int c = v[j].second;
      if (y & 1) {
        g[0][y] = c;
      } else {
        g[y][t] = c;
      }
    }
    ans += dinic();
  }
  cout << ans << endl;
  return 0;
}
