#include <bits/stdc++.h>
using namespace std;
int N;
int C[512][512];
int F[512][512];
vector<int> G[512];
int coada[512];
int viz[512];
int BFS[512];
inline int bfs(int sursa, int sink) {
  memset(viz, 0, sizeof(viz));
  coada[0] = 0;
  coada[++coada[0]] = sursa;
  viz[sursa] = 1;
  for (int i = 1; i <= coada[0]; ++i) {
    int nod = coada[i];
    if (nod == sink) continue;
    for (int j = 0; j < G[nod].size(); ++j) {
      int nod2 = G[nod][j];
      if (C[nod][nod2] == F[nod][nod2] || viz[nod2]) continue;
      viz[nod2] = 1;
      coada[++coada[0]] = nod2;
      BFS[nod2] = nod;
    }
  }
  return viz[sink];
}
int max_flow(int sursa, int sink) {
  int flow = 0;
  while (bfs(sursa, sink)) {
    for (int i = 0; i < G[sink].size(); ++i) {
      int nod = G[sink][i];
      if (F[nod][sink] == C[nod][sink] || !viz[nod]) continue;
      int cresc = C[nod][sink] - F[nod][sink];
      BFS[sink] = nod;
      for (nod = sink; nod != sursa; nod = BFS[nod])
        cresc = min(cresc, C[BFS[nod]][nod] - F[BFS[nod]][nod]);
      if (cresc == 0) continue;
      for (nod = sink; nod != sursa; nod = BFS[nod]) {
        F[BFS[nod]][nod] += cresc;
        F[nod][BFS[nod]] -= cresc;
      }
      flow += cresc;
    }
  }
  return flow;
}
int a[101];
int p[101][2];
int INF = 9999999;
int n, m;
void add(int a, int b, int c) {
  G[a].push_back(b);
  G[b].push_back(a);
  C[a][b] = c;
}
struct info {
  int p, k, idx;
};
vector<info> v[101];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= m; ++i) {
    cin >> p[i][0] >> p[i][1];
    if (p[i][0] % 2 == 1) swap(p[i][0], p[i][1]);
  }
  N = n;
  int sursa = ++N;
  int sink = ++N;
  for (int i = 1; i <= n; i++) {
    int x = a[i];
    for (int p = 2; p * p <= x; ++p)
      if (x % p == 0) {
        int cnt = 0;
        while (x % p == 0) {
          ++cnt;
          x /= p;
        }
        info now;
        now.p = p;
        now.k = cnt;
        now.idx = ++N;
        v[i].push_back(now);
      }
    if (x != 1) {
      info now;
      now.p = x;
      now.k = 1;
      now.idx = ++N;
      v[i].push_back(now);
    }
  }
  for (int i = 2; i <= n; i += 2) {
    for (int j = 0; j < v[i].size(); ++j) {
      info now = v[i][j];
      add(sursa, now.idx, now.k);
    }
  }
  for (int i = 1; i <= n; i += 2) {
    for (int j = 0; j < v[i].size(); ++j) {
      info now = v[i][j];
      add(now.idx, sink, now.k);
    }
  }
  for (int i = 1; i <= m; ++i) {
    int a = p[i][0], b = p[i][1];
    for (int j = 0; j < v[a].size(); ++j)
      for (int k = 0; k < v[b].size(); ++k)
        if (v[a][j].p == v[b][k].p) {
          add(v[a][j].idx, v[b][k].idx, INF);
        }
  }
  cout << max_flow(sursa, sink) << '\n';
  return 0;
}
