#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << "{" << p.first << "," << p.second << "}";
  return os;
}
const int N = 3e5 + 5;
const int oo = 1e9 + 7;
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) {}
  int 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));
    return G[from].back();
  }
  void removeEdge(int from, int to, int cap) {
    edges.pop_back();
    G[to].pop_back();
    edges.pop_back();
    G[from].pop_back();
  }
  void clear() {
    for (edge &e : edges) e.flow = 0;
    fill(h.begin(), h.end(), 0);
    fill(count.begin(), count.end(), 0);
    fill(inQ.begin(), inQ.end(), 0);
    fill(excess.begin(), excess.end(), 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];
  }
};
int a[N];
int x[N];
int y[N];
set<int> st;
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    int z = a[i];
    for (int j = 2; j * j <= z; j++) {
      if (z % j == 0) {
        st.insert(j);
        while (z % j == 0) z /= j;
      }
    }
    if (z > 1) st.insert(z);
  }
  for (int i = 0; i < m; i++) {
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
    if (x[i] % 2) swap(x[i], y[i]);
  }
  int ans = 0;
  for (int p : st) {
    PushRelabel g(n + 2);
    for (int i = 0; i < n; i++) {
      int cnt = 0;
      int z = a[i];
      while (z % p == 0) z /= p, cnt++;
      if (i % 2)
        g.addEdge(i, n + 1, cnt);
      else
        g.addEdge(n, i, cnt);
    }
    for (int i = 0; i < m; i++) {
      g.addEdge(x[i], y[i], 100);
    }
    ans += g.getFlow(n, n + 1);
  }
  cout << ans << '\n';
}
