#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
vector<pair<int, int> > a[105];
int cnt, s, t, head[2000], d[2000], cur[2000];
struct node {
  int v, c, next;
} g[100010 << 1];
void add(int a, int b, int c) {
  g[cnt].v = b, g[cnt].c = c, g[cnt].next = head[a], head[a] = cnt++;
  g[cnt].v = a, g[cnt].c = 0, g[cnt].next = head[b], head[b] = cnt++;
}
int bfs() {
  for (int i = 0; i <= t; i++) d[i] = -1, cur[i] = head[i];
  d[s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i + 1; i = g[i].next) {
      int j = g[i].v;
      if (g[i].c && d[j] == -1) d[j] = d[u] + 1, q.push(j);
    }
  }
  return d[t] >= 0;
}
int dfs(int u, int t, int lim) {
  if (u == t || lim == 0) return lim;
  int ans = 0, f;
  for (int &i = cur[u]; i + 1; i = g[i].next) {
    int j = g[i].v;
    if (d[j] == d[u] + 1 && (f = dfs(j, t, min(lim, g[i].c)))) {
      g[i].c -= f, g[i ^ 1].c += f;
      ans += f;
      lim -= f;
      if (lim == 0) break;
    }
  }
  d[u] = -1;
  return ans;
}
int max_flow() {
  int ans = 0;
  while (bfs()) ans += dfs(s, t, 1000000007);
  return ans;
}
int main() {
  int i, j, k, ca = 0, m, n, q;
  while (~scanf("%d%d", &n, &q)) {
    int sz = 0;
    map<int, int> g;
    for (i = 1; i <= n; i++) {
      scanf("%d", &j);
      a[i].clear();
      for (k = 2; k <= j / k; k++)
        if (j % k == 0) {
          m = 0;
          if (!g[k]) g[k] = ++sz;
          while (j % k == 0) j /= k, m++;
          a[i].push_back(make_pair(g[k], m));
        }
      if (j > 1) {
        if (!g[j]) g[j] = ++sz;
        a[i].push_back(make_pair(g[j], 1));
      }
      sort(a[i].begin(), a[i].end());
    }
    s = 0, t = n * sz + 1;
    cnt = 0;
    memset(head, -1, sizeof(head));
    for (i = 1; i <= n; i++) {
      if (i & 1) {
        for (j = 0; j < a[i].size(); j++)
          add(s, (i - 1) * sz + a[i][j].first, a[i][j].second);
      } else {
        for (j = 0; j < a[i].size(); j++)
          add((i - 1) * sz + a[i][j].first, t, a[i][j].second);
      }
    }
    while (q--) {
      scanf("%d%d", &i, &j);
      if (i % 2 == 0) swap(i, j);
      for (k = 0; k < a[i].size(); k++) {
        int first = a[i][k].first;
        int r = lower_bound(a[j].begin(), a[j].end(), make_pair(first, 0)) -
                a[j].begin();
        if (r >= a[j].size() || a[j][r].first > first) continue;
        add((i - 1) * sz + first, (j - 1) * sz + first,
            min(a[i][k].second, a[j][r].second));
      }
    }
    int ans = max_flow();
    printf("%d\n", ans);
  }
}
