#include <bits/stdc++.h>
const int N = 1e5 + 5, M = 8e5 + 5, INF = 1e9;
using namespace std;
int d[N], now[N];
int head[N], nt[M], to[M], val[M];
int n, m, s, t, ans, num = 1;
vector<int> pri[N], sum[N];
bool BFS() {
  register int i, y;
  for (i = s; i <= t; ++i) d[i] = 0;
  queue<int> q;
  q.push(s);
  now[s] = head[s];
  d[s] = 1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (i = head[x]; i; i = nt[i]) {
      if (d[y = to[i]] || !val[i]) continue;
      q.push(y);
      d[y] = d[x] + 1;
      now[y] = head[y];
      if (y == t) return true;
    }
  }
  return false;
}
int dinic(int p, int flow) {
  if (p == t) return flow;
  register int i, y, res = flow;
  for (i = now[p]; i && res; i = nt[i]) {
    if (d[y = to[i]] != d[p] + 1 || !val[i]) continue;
    int k = dinic(y, min(val[i], res));
    if (!k) d[y] = 0;
    val[i] -= k;
    val[i ^ 1] += k;
    res -= k;
  }
  now[p] = i;
  return flow - res;
}
inline void Add(int x, int y, int z) {
  ++num;
  nt[num] = head[x];
  head[x] = num;
  to[num] = y;
  val[num] = z;
  ++num;
  nt[num] = head[y];
  head[y] = num;
  to[num] = x;
  val[num] = 0;
}
void Make(int p, int v) {
  register int i;
  int l = sqrt(v);
  for (i = 2; i <= l; ++i) {
    int cnt = 0;
    while (!(v % i)) ++cnt, v /= i;
    if (cnt) sum[p].push_back(cnt), pri[p].push_back(i);
  }
  if (v > 1) sum[p].push_back(1), pri[p].push_back(v);
}
inline int T(int i, int j) { return (i - 1) * 30 + j + 1; }
void Upda(int u, int v) {
  register int i, j;
  for (i = 0; i != pri[u].size(); ++i)
    for (j = 0; j != pri[v].size(); ++j)
      if (pri[u][i] == pri[v][j])
        Add(T(u, i), T(v, j), min(sum[u][i], sum[v][j]));
}
int main() {
  register int i, j, x, y, z;
  scanf("%d%d", &n, &m);
  s = 0;
  t = n * 30 + 1;
  for (i = 1; i <= n; ++i) {
    scanf("%d", &x);
    Make(i, x);
    if (i & 1)
      for (j = 0; j != pri[i].size(); ++j) Add(s, T(i, j), sum[i][j]);
    else
      for (j = 0; j != pri[i].size(); ++j) Add(T(i, j), t, sum[i][j]);
  }
  for (i = 1; i <= m; ++i) {
    scanf("%d%d", &x, &y);
    if (y & 1) swap(x, y);
    Upda(x, y);
  }
  int flow = 0;
  while (BFS())
    while (flow = dinic(s, INF)) ans += flow;
  printf("%d\n", ans);
  return 0;
}
