#include <bits/stdc++.h>
using namespace std;
bool check(int n, int pos) { return n & (1LL << pos); }
int Set(int n, int pos) { return n = n | (1LL << pos); }
namespace dinic {
const int inf = (1e16);
const int maxn = 5005, maxe = 3000005;
int src, snk, nNode, nEdge;
int Q[maxn], last_edge[maxn], pro[maxn], dist[maxn];
int flow[2 * maxe], cap[2 * maxe], prev_edge[2 * maxe], to[2 * maxe];
void init(int _src, int _snk, int _n) {
  src = _src;
  snk = _snk;
  nNode = _n;
  nEdge = 0;
  memset(last_edge, -1, sizeof last_edge);
}
void addedge(int u, int v, int c, int bi = 0) {
  to[nEdge] = v, cap[nEdge] = c, flow[nEdge] = 0,
  prev_edge[nEdge] = last_edge[u], last_edge[u] = nEdge++;
  to[nEdge] = u, cap[nEdge] = (bi == 1 ? c : 0), flow[nEdge] = 0,
  prev_edge[nEdge] = last_edge[v], last_edge[v] = nEdge++;
}
bool bfs() {
  int st, en;
  memset(dist, -1, sizeof dist);
  dist[src] = st = en = 0;
  Q[en++] = src;
  while (st < en) {
    int u = Q[st++];
    for (int i = last_edge[u]; i >= 0; i = prev_edge[i]) {
      int v = to[i];
      if (flow[i] < cap[i] && dist[v] == -1) {
        dist[v] = dist[u] + 1;
        Q[en++] = v;
      }
    }
  }
  return dist[snk] != -1;
}
int dfs(int u, int fl) {
  if (u == snk) return fl;
  for (int &e = pro[u]; e >= 0; e = prev_edge[e]) {
    int v = to[e];
    if (flow[e] < cap[e] && (dist[v] == dist[u] + 1)) {
      int df = dfs(v, min(cap[e] - flow[e], fl));
      if (df > 0) {
        flow[e] += df;
        flow[e ^ 1] -= df;
        return df;
      }
    }
  }
  return 0;
}
int maxflow() {
  int ret = 0;
  while (bfs()) {
    for (int i = 0; i <= nNode; i++) pro[i] = last_edge[i];
    while (true) {
      int df = dfs(src, inf);
      if (df)
        ret += df;
      else
        break;
    }
  }
  return ret;
}
};  // namespace dinic
using namespace dinic;
const int maxxn = 50002;
vector<int> primes;
bool vis[maxxn + 10];
void sieve() {
  vis[0] = 1;
  vis[1] = 1;
  for (int i = 4; i <= maxxn; i += 2) {
    vis[i] = 1;
  }
  for (int i = 3; i * i <= maxxn; i += 2) {
    if (vis[i] == 0)
      for (int j = i * i; j <= maxxn; j += i) {
        vis[j] = 1;
      }
  }
  for (int i = 2; i <= maxxn; i++) {
    if (vis[i] == false) primes.push_back(i);
  }
}
vector<pair<long long, long long> > fact[105];
int main() {
  int i, j, k, l, m, n, o, r, q;
  int testcase;
  int input, flag, tag, ans;
  sieve();
  while (cin >> n >> m) {
    int nodecnt = 2;
    for (i = 1; i <= n; i++) fact[i].clear();
    for (i = 1; i <= n; i++) {
      scanf("%d", &input);
      for (j = 0; primes[j] * primes[j] <= input; j++) {
        while (input % primes[j] == 0) {
          fact[i].push_back({primes[j], nodecnt});
          input /= primes[j];
          nodecnt++;
        }
      }
      if (input > 1) {
        fact[i].push_back({input, nodecnt});
        nodecnt++;
      }
    }
    dinic ::init(1, nodecnt, nodecnt);
    for (i = 1; i <= m; i++) {
      int u, v;
      scanf("%d", &u);
      scanf("%d", &v);
      for (auto it : fact[u]) {
        for (auto jt : fact[v]) {
          if (it.first == jt.first) {
            if (u & 1) {
              dinic ::addedge(it.second, jt.second, 1);
            } else {
              dinic ::addedge(jt.second, it.second, 1);
            }
          }
        }
      }
    }
    for (i = 1; i <= n; i++) {
      if (i & 1)
        for (auto it : fact[i]) dinic ::addedge(1, it.second, 1);
      else
        for (auto it : fact[i]) dinic ::addedge(it.second, nodecnt, 1);
    }
    ans = dinic ::maxflow();
    cout << ans << '\n';
  }
}
