#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 11;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
long long read() {
  long long x = 0, f = 1;
  register 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;
}
int to[MAXN << 1], nxt[MAXN << 1], cap[MAXN << 1], flow[MAXN << 1];
int head[MAXN], tot;
void init() {
  memset(head, -1, sizeof head);
  tot = 0;
}
void add(int u, int v, int w) {
  to[tot] = v;
  nxt[tot] = head[u];
  cap[tot] = w;
  flow[tot] = 0;
  head[u] = tot++;
  swap(u, v);
  to[tot] = v;
  nxt[tot] = head[u];
  cap[tot] = 0;
  flow[tot] = 0;
  head[u] = tot++;
}
int n, m, s, t;
int dis[MAXN], pre[MAXN], cur[MAXN], gap[MAXN];
bool vis[MAXN];
struct QUEUE {
  int que[MAXN];
  int front, rear;
  void init() { front = rear = 0; }
  void push(int u) { que[rear++] = u; }
  int pop() { return que[front++]; }
  bool empty() { return front == rear; }
} que;
void bfs() {
  memset(vis, 0, sizeof vis);
  que.init();
  que.push(t);
  vis[t] = 1;
  dis[t] = 0;
  while (que.empty() ^ 1) {
    int u = que.pop();
    for (int i = head[u]; ~i; i = nxt[i]) {
      register int v = to[i], c = cap[i ^ 1], f = flow[i ^ 1];
      if (!vis[v] && c > f) {
        vis[v] = 1;
        dis[v] = dis[u] + 1;
        que.push(v);
      }
    }
  }
}
int aug() {
  int u = t, ans = INF;
  while (u != s) {
    ans = min(ans, cap[pre[u]] - flow[pre[u]]);
    u = to[pre[u] ^ 1];
  }
  u = t;
  while (u != s) {
    flow[pre[u]] += ans;
    flow[pre[u] ^ 1] -= ans;
    u = to[pre[u] ^ 1];
  }
  return ans;
}
int isap() {
  int ans = 0;
  bfs();
  memset(gap, 0, sizeof gap);
  memcpy(cur, head, sizeof head);
  for (int i = 1; i <= n; i++) gap[dis[i]]++;
  int u = s;
  while (dis[s] < n) {
    if (u == t) {
      ans += aug();
      u = s;
    }
    bool ok = 0;
    for (int i = cur[u]; ~i; i = nxt[i]) {
      int v = to[i], c = cap[i], f = flow[i];
      if (c > f && dis[u] == dis[v] + 1) {
        ok = 1;
        pre[v] = i;
        cur[u] = i;
        u = v;
        break;
      }
    }
    if (!ok) {
      int mn = n - 1;
      for (int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i], c = cap[i], f = flow[i];
        if (c > f) mn = min(mn, dis[v]);
      }
      if (--gap[dis[u]] == 0) break;
      dis[u] = mn + 1;
      gap[dis[u]]++;
      cur[u] = head[u];
      if (u != s) u = to[pre[u] ^ 1];
    }
  }
  return ans;
}
int a[MAXN], b[MAXN][2], v;
long long solve(int x) {
  init();
  s = 2 * v + 1;
  t = s + 1;
  n = t;
  for (register int i = 1; i <= v; i++) {
    int num = 0;
    while (a[i] % x == 0) num++, a[i] /= x;
    if (i & 1)
      add(s, i, num);
    else
      add(i + v, t, num);
  }
  for (register int i = 1; i <= m; i++) add(b[i][0], b[i][1] + v, INF);
  return isap();
}
int main() {
  while (cin >> v >> m) {
    for (register int i = 1; i <= v; i++) a[i] = read();
    for (register int i = 1; i <= m; i++) {
      b[i][0] = read();
      b[i][1] = read();
      if (b[i][1] & 1) swap(b[i][0], b[i][1]);
    }
    long long ans = 0;
    for (register int i = 1; i <= v; i++) {
      int block = sqrt(a[i]) + 1;
      for (register int j = 2; j <= block; j++) {
        if (a[i] % j == 0) ans += solve(j);
      }
      if (a[i] > 1) ans += solve(a[i]);
    }
    printf("%lld\n", (long long)ans);
  }
  return 0;
}
