#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
const int maxm = 12345;
int n, m, x;
int link[maxm], tot;
bool vis[maxm];
vector<pair<int, int> > F[maxn];
vector<int> G[maxm];
bool dfs(int u) {
  for (auto &v : G[u]) {
    if (vis[v]) continue;
    vis[v] = 1;
    if (link[v] == -1 || dfs(link[v])) {
      link[v] = u;
      return 1;
    }
  }
  return 0;
}
int hungary() {
  int cnt = 0;
  memset(link, -1, sizeof link);
  for (int i = 1; i <= tot; i++) {
    memset(vis, 0, sizeof vis);
    cnt += dfs(i);
  }
  return cnt;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    for (int j = 2; j * j <= x; j++) {
      while (x % j == 0) {
        F[i].push_back(pair<int, int>(j, ++tot));
        x /= j;
      }
    }
    if (x > 1) F[i].push_back(pair<int, int>(x, ++tot));
  }
  while (m--) {
    int i, j;
    scanf("%d%d", &i, &j);
    if (i & 1) swap(i, j);
    for (auto &u : F[i])
      for (auto &v : F[j])
        if (u.first == v.first) G[u.second].push_back(v.second);
  }
  cout << hungary() << endl;
  return 0;
}
