#include <bits/stdc++.h>
using namespace std;
int dp, pre[810], p[810], tt[810], g[810], vis[810], dis[810], z[100010],
    now[810], s, t, a[100010], sum[100010];
int n, m, i, L[100010], R[100010], flag, j, ans;
void link(int x, int y, int z) {
  dp++;
  pre[dp] = p[x];
  p[x] = dp;
  tt[dp] = y;
  g[dp] = z;
  dp++;
  pre[dp] = p[y];
  p[y] = dp;
  tt[dp] = x;
  g[dp] = 0;
}
int min(int a, int b) {
  if (a < b) return a;
  return b;
}
int bfs() {
  int i, head, tail;
  memcpy(now, p, sizeof(p));
  memset(vis, 0, sizeof(vis));
  head = 0;
  tail = 1;
  vis[s] = 1;
  dis[s] = 0;
  z[tail] = s;
  do {
    head++;
    i = p[z[head]];
    while (i) {
      if ((vis[tt[i]] == 0) && (g[i] > 0)) {
        vis[tt[i]] = 1;
        dis[tt[i]] = dis[z[head]] + 1;
        tail++;
        z[tail] = tt[i];
      }
      i = pre[i];
    }
  } while (head != tail);
  return vis[t];
}
int dfs(int u, int flow) {
  int ans, tmp, i;
  if (u == t) return flow;
  i = now[u];
  ans = 0;
  while (i) {
    if ((dis[u] + 1 == dis[tt[i]]) && (g[i] > 0)) {
      tmp = dfs(tt[i], min(flow - ans, g[i]));
      ans += tmp;
      g[i] -= tmp;
      if (i % 2 == 1)
        g[i + 1] += tmp;
      else
        g[i - 1] += tmp;
      if (flow == ans) return flow;
    }
    i = pre[i];
    now[u] = i;
  }
  if (flow > ans) dis[u] = 1;
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (i = 1; i <= m; i++) scanf("%d%d", &L[i], &R[i]);
  for (i = 2; i <= 35000; i++) {
    flag = 0;
    for (j = 1; j <= n; j++)
      if (a[j] % i == 0) {
        flag = 1;
        while (a[j] % i == 0) {
          sum[j]++;
          a[j] = a[j] / i;
        }
      }
    if (flag) {
      dp = 0;
      memset(p, 0, sizeof(p));
      s = 0;
      t = n + 1;
      for (j = 1; j <= n; j++)
        if (j % 2 == 0)
          link(j, t, sum[j]);
        else
          link(s, j, sum[j]);
      for (j = 1; j <= m; j++)
        if (L[j] % 2 == 0)
          link(R[j], L[j], 0x37373737);
        else
          link(L[j], R[j], 0x37373737);
      while (bfs()) ans = ans + dfs(s, 0x37373737);
      for (j = 1; j <= n; j++) sum[j] = 0;
    }
    flag = 0;
  }
  for (i = 1; i <= n; i++)
    if (a[i] > 1) {
      flag = a[i];
      for (j = 1; j <= n; j++)
        while (a[j] % flag == 0) {
          sum[j]++;
          a[j] = a[j] / flag;
        }
      dp = 0;
      memset(p, 0, sizeof(p));
      s = 0;
      t = n + 1;
      for (j = 1; j <= n; j++)
        if (j % 2 == 0)
          link(j, t, sum[j]);
        else
          link(s, j, sum[j]);
      for (j = 1; j <= m; j++)
        if (L[j] % 2 == 0)
          link(R[j], L[j], 0x37373737);
        else
          link(L[j], R[j], 0x37373737);
      while (bfs()) ans = ans + dfs(s, 0x37373737);
      for (j = 1; j <= n; j++) sum[j] = 0;
    }
  printf("%d", ans);
}
