#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
struct _EDGE {
  long long u, v;
  long long cap, fl;
  _EDGE(long long uu, long long vv, long long capp, long long fll) {
    u = uu, v = vv, cap = capp, fl = fll;
  }
};
struct FLOW {
  const long long inf = 0x3f3f3f3f3f3f3f3f;
  vector<vector<long long>> adj;
  vector<_EDGE> edges;
  vector<long long> lvl, frm;
  queue<long long> q;
  long long st, ed, nd = 0, n;
  FLOW(long long s, long long e, long long nn) {
    st = s, ed = e, n = nn;
    lvl.resize(n);
    frm.resize(n);
    adj.resize(n);
  }
  void addedge(long long u, long long v, long long cap) {
    edges.push_back(_EDGE(u, v, cap, 0));
    edges.push_back(_EDGE(v, u, 0, 0));
    adj[u].push_back(nd);
    adj[v].push_back(nd ^ 1);
    nd += 2;
  }
  bool bfs() {
    fill(lvl.begin(), lvl.end(), -1);
    q.push(st);
    lvl[st] = 0;
    while (!q.empty()) {
      long long u = q.front();
      q.pop();
      for (auto x : adj[u]) {
        if (edges[x].cap - edges[x].fl > 0 && lvl[edges[x].v] == -1) {
          lvl[edges[x].v] = lvl[u] + 1;
          q.push(edges[x].v);
        }
      }
    }
    return lvl[ed] != -1;
  }
  long long dfs(long long u, long long fl) {
    if (!fl || u == ed) return fl;
    for (; frm[u] < adj[u].size(); frm[u]++) {
      long long x = adj[u][frm[u]];
      if (lvl[u] + 1 == lvl[edges[x].v]) {
        long long p = dfs(edges[x].v, min(fl, edges[x].cap - edges[x].fl));
        if (p) {
          edges[x].fl += p;
          edges[x ^ 1].fl -= p;
          return p;
        }
      }
    }
    return 0;
  }
  long long dinic() {
    long long flow = 0;
    while (bfs()) {
      fill(frm.begin(), frm.end(), 0);
      while (long long x = dfs(st, inf)) flow += x;
    }
    return flow;
  }
  void mem() {
    for (long long i = 0; i < nd; i++) edges[i].fl = 0;
  }
  void show() {
    for (int i = 0; i < nd; i++)
      cout << edges[i].u << " " << edges[i].v << " " << edges[i].cap << " "
           << edges[i].fl << "\n";
  }
};
bool ar[100009];
vector<long long> prm;
vector<pair<long long, long long>> vc[109];
void seive() {
  for (long long i = 4; i <= 100000; i += 2) ar[i] = true;
  for (long long i = 3; i * i <= 100000; i += 2) {
    if (!ar[i]) {
      for (long long j = i * i; j <= 100000; j += 2 * i) ar[j] = true;
    }
  }
  for (long long i = 2; i <= 100000; i++)
    if (!ar[i]) prm.push_back(i);
}
void facto(long long n, long long id) {
  for (auto x : prm) {
    if (n % x == 0) {
      long long cnt = 0;
      while (n % x == 0) {
        cnt++;
        n /= x;
      }
      vc[id].push_back({x, cnt});
    }
  }
  if (n != 1) vc[id].push_back({n, 1});
}
int main() {
  FLOW G(0, 4000, 4009);
  long long n, m;
  cin >> n >> m;
  for (long long i = 1; i <= n; i += 2) G.addedge(0, i, INF);
  for (long long i = 2; i <= n; i += 2) G.addedge(i, 4000, INF);
  seive();
  long long nd = n;
  for (long long i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    facto(x, i);
    for (long long j = 0; j < vc[i].size(); j++) {
      if (i % 2)
        G.addedge(i, ++nd, vc[i][j].second);
      else
        G.addedge(++nd, i, vc[i][j].second);
      vc[i][j].second = nd;
    }
  }
  for (int i = 1; i <= m; i++) {
    long long a, b;
    cin >> a >> b;
    if (b % 2) swap(a, b);
    for (long long j = 0, k = 0; j < vc[a].size() && k < vc[b].size();) {
      if (vc[a][j].first == vc[b][k].first) {
        G.addedge(vc[a][j].second, vc[b][k].second, INF);
        j++;
        k++;
      } else if (vc[a][j].first > vc[b][k].first)
        k++;
      else
        j++;
    }
  }
  cout << G.dinic();
  return 0;
}
