#include <bits/stdc++.h>
using namespace std;
long long int power(long long int x, long long int y) {
  long long int res = 1;
  while (y) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y / 2, x = (x * x) % 1000000007;
  }
  return res % 1000000007;
}
map<long long int, vector<long long int> > haha[101];
vector<vector<long long int> > prime(101);
struct edge {
  int from, to;
  int cap, flow;
  edge(int from, int to, int cap, int flow = 0)
      : from(from), to(to), cap(cap), flow(flow) {}
};
struct PushRelabel {
  int N;
  vector<edge> edges;
  vector<vector<int> > G;
  vector<int> h, inQ, count;
  vector<int> excess;
  queue<int> Q;
  PushRelabel(int N) : N(N), count(N << 1), G(N), h(N), inQ(N), excess(N) {}
  void addEdge(int from, int to, int cap) {
    G[from].push_back(edges.size());
    edges.push_back(edge(from, to, cap));
    G[to].push_back(edges.size());
    edges.push_back(edge(to, from, 0));
  }
  void enQueue(int u) {
    if (!inQ[u] && excess[u] > 0) Q.push(u), inQ[u] = true;
  }
  void Push(int edgeIdx) {
    edge& e = edges[edgeIdx];
    int toPush = min<int>(e.cap - e.flow, excess[e.from]);
    if (toPush > 0 && h[e.from] > h[e.to]) {
      e.flow += toPush;
      excess[e.to] += toPush;
      excess[e.from] -= toPush;
      edges[edgeIdx ^ 1].flow -= toPush;
      enQueue(e.to);
    }
  }
  void Relabel(int u) {
    count[h[u]] -= 1;
    h[u] = 2 * N - 2;
    for (int i = 0; i < G[u].size(); ++i) {
      edge& e = edges[G[u][i]];
      if (e.cap > e.flow) h[u] = min(h[u], h[e.to]);
    }
    count[++h[u]] += 1;
  }
  void gapRelabel(int height) {
    for (int u = 0; u < N; ++u)
      if (h[u] >= height && h[u] < N) {
        count[h[u]] -= 1;
        count[h[u] = N] += 1;
        enQueue(u);
      }
  }
  void Discharge(int u) {
    for (int i = 0; excess[u] > 0 && i < G[u].size(); ++i) {
      Push(G[u][i]);
    }
    if (excess[u] > 0) {
      if (h[u] < N && count[h[u]] < 2)
        gapRelabel(h[u]);
      else
        Relabel(u);
    } else if (!Q.empty()) {
      Q.pop();
      inQ[u] = false;
    }
  }
  int getFlow(int src, int snk) {
    h[src] = N;
    inQ[src] = inQ[snk] = true;
    count[0] = N - (count[N] = 1);
    for (int i = 0; i < G[src].size(); ++i) {
      excess[src] += edges[G[src][i]].cap;
      Push(G[src][i]);
    }
    while (!Q.empty()) {
      Discharge(Q.front());
    }
    return excess[snk];
  }
};
void example() {
  int n, m;
  cin >> n >> m;
  PushRelabel df(n);
  while (m--) {
    int x, y, c;
    cin >> x >> y >> c;
    --x, --y;
    if (x != y) {
      df.addEdge(x, y, c);
      df.addEdge(y, x, c);
    }
  }
  cout << df.getFlow(0, n - 1) << "\n";
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int n, m;
  cin >> n >> m;
  long long int i, j;
  long long int cnt = 1;
  for (i = 1; i <= n; i++) {
    long long int k;
    cin >> k;
    for (j = 2; j * j <= k; j++) {
      if (k % j == 0) {
        while (k % j == 0) {
          haha[i][j].push_back(cnt++);
          k /= j;
        }
        prime[i].push_back(j);
      }
    }
    if (k > 1) haha[i][k].push_back(cnt++), prime[i].push_back(k);
  }
  PushRelabel df(cnt + 1);
  set<long long int> firstpart;
  set<long long int> secondpart;
  while (m--) {
    long long int u, v;
    cin >> u >> v;
    if (u % 2 == 0) swap(u, v);
    for (i = 0; i < prime[u].size(); i++) {
      if (haha[v].find(prime[u][i]) == haha[v].end()) continue;
      for (auto uu : haha[u][prime[u][i]]) {
        for (auto vv : haha[v][prime[u][i]]) {
          firstpart.insert(uu);
          secondpart.insert(vv);
          df.addEdge(uu, vv, 1);
        }
      }
    }
  }
  for (auto v : firstpart) df.addEdge(0, v, 1);
  for (auto v : secondpart) df.addEdge(v, cnt, 1);
  cout << df.getFlow(0, cnt) << "\n";
}
