#include <bits/stdc++.h>
using namespace std;
function<void(void)> ____ = []() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
};
const int MAXN = 2222;
const int INF = 0x3f3f3f3f;
int n, m, A[MAXN], ID;
vector<int> g[MAXN];
pair<int, int> pr[MAXN];
map<int, pair<int, int> > msk[MAXN];
struct EDGE {
  int to, cap, rev;
  EDGE(){};
  EDGE(int to, int cap, int rev) : to(to), cap(cap), rev(rev){};
};
vector<EDGE> G[MAXN];
int iter[MAXN], rk[MAXN];
void ADDEDGE(int u, int v, int cap) {
  G[u].push_back(EDGE(v, cap, (int)G[v].size()));
  G[v].push_back(EDGE(u, 0, (int)G[u].size() - 1));
}
bool bfs() {
  memset(rk, 0, sizeof(rk));
  memset(iter, 0, sizeof(iter));
  rk[0] = 1;
  queue<int> que;
  que.push(0);
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (auto e : G[u]) {
      if (!e.cap or rk[e.to]) continue;
      rk[e.to] = rk[u] + 1;
      que.push(e.to);
    }
  }
  return rk[MAXN - 1] != 0;
}
int dfs(int u, int flow) {
  if (u == MAXN - 1) return flow;
  for (int &i = iter[u]; i < (int)G[u].size(); i++) {
    auto &e = G[u][i];
    if (!e.cap or rk[e.to] != rk[u] + 1) continue;
    int d = dfs(e.to, min(e.cap, flow));
    if (d) {
      e.cap -= d;
      G[e.to][e.rev].cap += d;
      return d;
    }
  }
  return 0;
}
int Dinic() {
  int flow = 0;
  while (bfs()) {
    int d = dfs(0, INF);
    while (d) {
      flow += d;
      d = dfs(0, INF);
    }
  }
  return flow;
}
void build() {
  for (int i = 1; i <= n; i++) {
    int x = A[i];
    for (int f = 2; f * f <= x; f++) {
      if (x % f != 0) continue;
      msk[i].insert(make_pair(f, make_pair(0, ++ID)));
      while (x % f == 0) {
        x /= f;
        msk[i][f].first++;
      }
    }
    if (x != 1) msk[i].insert(make_pair(x, make_pair(1, ++ID)));
  }
  for (int i = 1; i <= n; i++) {
    for (auto p : msk[i]) {
      if (i & 1)
        ADDEDGE(0, p.second.second, p.second.first);
      else
        ADDEDGE(p.second.second, MAXN - 1, p.second.first);
    }
    if (i & 1) {
      for (int v : g[i]) {
        for (auto p : msk[i]) {
          if (!msk[v].count(p.first)) continue;
          ADDEDGE(p.second.second, msk[v][p.first].second, INF);
        }
      }
    }
  }
}
int main() {
  ____();
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> A[i];
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    if (v & 1) swap(u, v);
    g[u].push_back(v);
  }
  build();
  cout << Dinic() << endl;
  return 0;
}
