#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, s, t;
int a[107], x[107], y[107];
vector<int> prime;
int mark[100007];
int num[107];
int head[107], cc;
struct Edge {
  int v, next, w;
} e[107 * 107];
void init() {
  memset(mark, -1, sizeof(mark));
  mark[1] = mark[0] = 0;
  prime.clear();
  for (int i = 2; i < 100007; i++) {
    if (~mark[i]) continue;
    prime.push_back(i);
    for (int j = 2 * i; j < 100007; j += i) mark[j] = i;
  }
}
void add(int u, int v, int w) {
  e[cc].v = v;
  e[cc].next = head[u];
  e[cc].w = w;
  head[u] = cc++;
  e[cc].v = u;
  e[cc].next = head[v];
  e[cc].w = 0;
  head[v] = cc++;
}
int d[107];
bool bfs(int s, int t) {
  queue<int> q;
  memset(d, 0, sizeof(d));
  d[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (u == t) return true;
    for (int i = head[u]; ~i; i = e[i].next) {
      int v = e[i].v;
      int w = e[i].w;
      if (!d[v] && w) {
        q.push(v);
        d[v] = d[u] + 1;
      }
    }
  }
  return false;
}
int dfs(int now, int maxf, int t) {
  if (now == t) return maxf;
  int ret = 0, f;
  for (int i = head[now]; ~i; i = e[i].next) {
    int v = e[i].v;
    int w = e[i].w;
    if (w && d[v] == d[now] + 1) {
      f = dfs(v, min(maxf - ret, w), t);
      e[i].w -= f;
      e[i ^ 1].w += f;
      ret += f;
      if (ret == maxf) return ret;
    }
  }
  return ret;
}
int dinic(int s, int t) {
  int ans = 0;
  while (bfs(s, t)) ans += dfs(s, (1 << 29), t);
  return ans;
}
bool judge(int num) {
  if (num <= sqrt(1e9)) return false;
  for (int i = 0; i < prime.size() && prime[i] * prime[i] <= num; i++)
    if (num % prime[i] == 0) return false;
  return true;
}
int main() {
  init();
  while (~scanf("%d%d", &n, &m)) {
    s = 0, t = n + 1;
    int ans = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) {
      scanf("%d%d", &x[i], &y[i]);
      if (y[i] & 1) swap(x[i], y[i]);
    }
    int lim = sqrt(1e9);
    for (int i = 2; i <= lim; i++) {
      if (~mark[i]) continue;
      memset(head, -1, sizeof(head));
      cc = 0;
      memset(num, 0, sizeof(num));
      for (int j = 1; j <= n; j++) {
        while (a[j] % i == 0) {
          num[j]++;
          a[j] /= i;
        }
      }
      for (int j = 1; j <= n; j += 2) add(s, j, num[j]);
      for (int j = 2; j <= n; j += 2) add(j, t, num[j]);
      for (int j = 0; j < m; j++) {
        int w = min(num[x[j]], num[y[j]]);
        add(x[j], y[j], w);
      }
      ans += dinic(s, t);
    }
    memset(head, -1, sizeof(head));
    cc = 0;
    for (int i = 1; i <= n; i += 2)
      if (judge(a[i])) add(s, i, 1);
    for (int i = 2; i <= n; i += 2)
      if (judge(a[i])) add(i, t, 1);
    for (int i = 0; i < m; i++)
      if (a[x[i]] != 1 && a[x[i]] == a[y[i]]) add(x[i], y[i], 1);
    ans += dinic(s, t);
    printf("%d\n", ans);
  }
}
