#include <bits/stdc++.h>
using namespace std;
long long qpow(long long a, long long b) {
  long long res = 1, base = a;
  while (b) {
    if (b % 2) res = res * base;
    base = base * base;
    b /= 2;
  }
  return res;
}
long long powmod(long long a, long long b) {
  long long res = 1, base = a;
  while (b) {
    if (b % 2) res = res * base % 1000000007;
    base = base * base % 1000000007;
    b /= 2;
  }
  return res;
}
struct Edge {
  int v, c, next;
  Edge() {}
  Edge(int v, int c, int next) : v(v), c(c), next(next) {}
} E[2000005];
queue<int> q;
int H[100005], cntE;
int dis[100005];
int cur[100005];
int cnt[100005];
int pre[100005];
int flow, s, t, nv;
int n, m, o;
int a[100005];
int x[100005];
vector<pair<int, int> > g[100005];
map<int, int> mpp;
map<int, int>::iterator it;
void addedges(int u, int v, int c) {
  E[cntE] = Edge(v, c, H[u]);
  H[u] = cntE++;
  E[cntE] = Edge(u, 0, H[v]);
  H[v] = cntE++;
}
void bfs(void) {
  memset(cnt, 0, sizeof cnt);
  memset(dis, -1, sizeof dis);
  cnt[0] = 1, dis[t] = 0;
  q.push(t);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int e = H[u]; ~e; e = E[e].next) {
      int v = E[e].v;
      if (dis[v] == -1) {
        dis[v] = dis[u] + 1;
        cnt[dis[v]]++;
        q.push(v);
      }
    }
  }
}
int isap(void) {
  memcpy(cur, H, sizeof cur);
  flow = 0;
  bfs();
  int u = pre[s] = s, e, minv, f, pos;
  while (dis[s] < nv) {
    if (u == t) {
      f = 0x3f3f3f3f;
      for (int i = s; i != t; i = E[cur[i]].v)
        if (E[cur[i]].c < f) {
          f = E[cur[i]].c;
          pos = i;
        }
      for (int i = s; i != t; i = E[cur[i]].v) {
        E[cur[i]].c -= f;
        E[cur[i] ^ 1].c += f;
      }
      flow += f;
      u = pos;
    }
    for (e = H[u]; ~e; e = E[e].next)
      if (E[e].c && dis[E[e].v] + 1 == dis[u]) break;
    if (~e) {
      cur[u] = e;
      pre[E[e].v] = u;
      u = E[e].v;
    } else {
      if (--cnt[dis[u]] == 0) break;
      for (e = H[u], minv = nv; ~e; e = E[e].next)
        if (E[e].c && minv > dis[E[e].v]) {
          minv = dis[E[e].v];
          cur[u] = e;
        }
      dis[u] = minv + 1;
      cnt[dis[u]]++;
      u = pre[u];
    }
  }
  return flow;
}
void init(void) {
  cntE = 0;
  mpp.clear();
  memset(H, -1, sizeof H);
}
void read(void) {
  int aa, bb;
  scanf("%d%d", &n, &m);
  s = 0, t = n + 1, o = n + 2;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    for (int j = 2; (long long)j * j <= a[i]; j++) {
      if (a[i] % j == 0) {
        int t = 0;
        while (a[i] % j == 0) a[i] /= j, t++;
        g[i].push_back(make_pair(j, t));
      }
    }
    if (a[i] != 1) g[i].push_back(make_pair(a[i], 1));
  }
  for (int i = 1; i <= n; i++) x[i] = g[i].size();
  for (int i = 1; i <= n; i++) x[i] += x[i - 1];
  while (m--) {
    scanf("%d%d", &aa, &bb);
    if (aa % 2 == 0) swap(aa, bb);
    for (int i = 0; i < g[aa].size(); i++)
      for (int j = 0; j < g[bb].size(); j++)
        if (g[aa][i].first == g[bb][j].first)
          addedges(x[aa - 1] + i + o, x[bb - 1] + j + o, 0x3f3f3f3f);
  }
  for (int i = 1; i <= n; i++)
    if (i % 2) {
      for (int j = 0; j < g[i].size(); j++)
        addedges(s, x[i - 1] + j + o, g[i][j].second);
    } else {
      for (int j = 0; j < g[i].size(); j++)
        addedges(x[i - 1] + j + o, t, g[i][j].second);
    }
  nv = x[n] + o + 1;
}
void work(void) { printf("%d\n", isap()); }
int main(void) {
  init();
  read();
  work();
  return 0;
}
