#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 4e4 + 5;
const int INF = 1e9;
struct Edge {
  int end, wi, next;
} edge[N * 10];
int first[N];
pair<int, int> pa[N];
int bo[M], a[N], n, m, num[N];
int tot, S, T;
void addedge(int x, int y, int s) {
  edge[tot] = (Edge){y, s, first[x]};
  first[x] = tot++;
}
void add(int x, int y, int s) {
  addedge(x, y, s);
  addedge(y, x, 0);
}
int h[N], cur[N];
int bfs() {
  static int queue[N];
  memset(h, -1, sizeof(h));
  h[S] = 0;
  int head = 1, tail = 1;
  queue[1] = S;
  while (head <= tail) {
    int x = queue[head++];
    for (int k = first[x]; ~k; k = edge[k].next)
      if (edge[k].wi && h[edge[k].end] == -1) {
        h[edge[k].end] = h[x] + 1;
        queue[++tail] = edge[k].end;
      }
  }
  return h[T] != -1;
}
int dfs(int x, int flow) {
  if (x == T) return flow;
  int ans = 0;
  for (int &k = cur[x]; ~k; k = edge[k].next) {
    int y = edge[k].end;
    if (h[y] == h[x] + 1 && edge[k].wi) {
      int tmp = dfs(y, min(flow, edge[k].wi));
      if (tmp > 0) {
        edge[k].wi -= tmp;
        edge[k ^ 1].wi += tmp;
        ans += tmp;
        break;
      }
    }
  }
  if (!ans) h[x] = -1;
  return ans;
}
int solve() {
  memset(first, -1, sizeof(first));
  tot = 0;
  for (int i = 1; i <= n; ++i)
    if (i & 1)
      add(i, T, num[i]);
    else
      add(S, i, num[i]);
  for (int i = 0; i < m; ++i) add(pa[i].first, pa[i].second, INF);
  int ans = 0;
  while (bfs()) {
    memcpy(cur, first, sizeof(cur));
    static int count = 0;
    int tmp;
    while (tmp = dfs(S, INF)) ans += tmp;
  }
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &pa[i].first, &pa[i].second);
    if (pa[i].first & 1) swap(pa[i].first, pa[i].second);
  }
  int ans = 0;
  S = n + 1, T = S + 1;
  for (int i = 2; i < M; ++i)
    if (!bo[i]) {
      for (int j = i * i; j < M; j += i) bo[j] = 1;
      int flag = 0;
      for (int j = 1; j <= n; ++j) {
        num[j] = 0;
        while (a[j] % i == 0) {
          a[j] /= i;
          num[j]++;
        }
        flag |= num[j];
      }
      if (flag) ans += solve();
    }
  for (int i = 1; i <= n; ++i)
    if (a[i] != 1) {
      int flag = 0;
      int tmp = a[i];
      for (int j = 1; j <= n; ++j) {
        num[j] = 0;
        while (a[j] % tmp == 0) {
          a[j] /= tmp;
          num[j]++;
        }
        flag |= num[i];
      }
      if (flag) ans += solve();
    }
  printf("%d\n", ans);
  return 0;
}
