#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
struct edge {
  int to, next, v;
} e[10 * 200010];
int head[200010];
int a[200010], h[200010], q[200010], u[200010], v[200010];
int n, m, cnt = 1, ans;
inline void ins(int u, int v, int w) {
  e[++cnt].v = w;
  e[cnt].to = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}
inline void insert(int u, int v, int w) {
  ins(u, v, w);
  ins(v, u, 0);
}
inline bool bfs() {
  memset(h, -1, sizeof(h));
  int t = 0, w = 1;
  q[1] = 0;
  h[0] = 0;
  while (t < w) {
    int now = q[++t];
    for (int j = head[now]; j; j = e[j].next) {
      if (e[j].v && h[e[j].to] == -1) {
        q[++w] = e[j].to;
        h[e[j].to] = h[now] + 1;
      }
    }
  }
  if (h[99999] == -1) return 0;
  return 1;
}
inline int dfs(int x, int f) {
  if (x == 99999 || f == 0) return f;
  int w, used = 0;
  for (int i = head[x]; i; i = e[i].next) {
    if (e[i].v && h[e[i].to] == h[x] + 1) {
      w = used;
      w = dfs(e[i].to, min(e[i].v, f - used));
      e[i].v -= w;
      e[i ^ 1].v += w;
      used += w;
      if (used == f) return f;
    }
  }
  if (!used) h[x] == -1;
  return used;
}
inline void dinic() {
  while (bfs()) ans += dfs(0, 0x3ffffff);
}
inline void solve(int x) {
  cnt = 1;
  memset(head, 0, sizeof(head));
  for (int i = 1; i <= n; i++) {
    int t = 0;
    while (a[i] % x == 0) t++, a[i] /= x;
    if (i & 1)
      insert(0, i, t);
    else
      insert(i + n, 99999, t);
  }
  for (int i = 1; i <= m; i++) insert(u[i], v[i] + n, 0x3ffffff);
  dinic();
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  for (int i = 1; i <= m; i++) {
    u[i] = read();
    v[i] = read();
    if (u[i] % 2 == 0) swap(u[i], v[i]);
  }
  for (int i = 1; i <= n; i++) {
    int t = sqrt(a[i]);
    for (int j = 2; j <= t; j++)
      if (a[i] % j == 0) solve(j);
    if (a[i] != 1) solve(a[i]);
  }
  printf("%d\n", ans);
  return 0;
}
