#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int MAXN = 5050;
const int MAXE = 1e6;
int n, m;
int v[N];
int good[N][2];
int sz[N];
int d[N][50];
int cnt[N][50];
int no[N][50];
int edge_cnt, src, snk, node_cnt, que_sz, front, rear;
int head[MAXN], work[MAXN], to[MAXE], cap[MAXE], nxt[MAXE];
int que[MAXN], dis[MAXN];
void add_edge(int f, int t, int c) {
  nxt[edge_cnt] = head[f];
  head[f] = edge_cnt;
  to[edge_cnt] = t;
  cap[edge_cnt] = c;
  edge_cnt++;
}
void add_bi_edge(int f, int t, int c) {
  add_edge(f, t, c);
  add_edge(t, f, 0);
}
bool bfs() {
  que_sz = front = rear = 0;
  que[que_sz++] = src;
  rear++;
  memset(dis, -1, sizeof dis);
  dis[src] = 0;
  while (que_sz) {
    int u = que[front];
    front++, --que_sz;
    for (int i = head[u]; i != -1; i = nxt[i]) {
      int v = to[i];
      if (cap[i] <= 0 || dis[v] != -1) continue;
      dis[v] = dis[u] + 1;
      que[rear] = v;
      rear++, que_sz++;
      if (v == snk) return 1;
    }
  }
  return 0;
}
int dfs(int u, int flow) {
  if (!flow) return 0;
  if (u == snk) return flow;
  for (int &i = work[u]; i != -1; i = nxt[i]) {
    if (dis[to[i]] != dis[u] + 1) continue;
    int f = dfs(to[i], min(flow, cap[i]));
    if (f) {
      cap[i] -= f;
      cap[i ^ 1] += f;
      return f;
    }
  }
  return 0;
}
int solve() {
  int ret = 0, flow = 0;
  while (bfs()) {
    memcpy(work, head, sizeof head);
    while (flow = dfs(src, MAXE)) ret += flow;
  }
  return ret;
}
int main() {
  memset(head, -1, sizeof head);
  scanf("%d%d", &n, &m);
  src = n;
  snk = n + 1;
  node_cnt = n + 2;
  for (int i = 0; i < int(n); i++) scanf("%d", &v[i]);
  for (int i = 0; i < int(m); i++)
    for (int j = 0; j < int(2); j++) {
      int x;
      scanf("%d", &x);
      good[i][j] = --x;
    }
  for (int i = 0; i < int(n); i++) {
    int k = 2, tmp = v[i], c = 0;
    while (k * k <= tmp) {
      if (tmp % k == 0) {
        d[i][sz[i]] = k;
        while (tmp % k == 0) {
          c++;
          tmp /= k;
        }
        cnt[i][sz[i]] = c;
        sz[i]++;
      }
      k++;
    }
    if (tmp != 1) {
      d[i][sz[i]] = tmp;
      cnt[i][sz[i]] = 1;
      sz[i]++;
    }
  }
  for (int i = 0; i < int(n); i++) {
    if (i % 2 == 0)
      add_bi_edge(src, i, MAXE);
    else
      add_bi_edge(i, snk, MAXE);
  }
  for (int i = 0; i < int(n); i++) {
    for (int j = 0; j < int(sz[i]); j++) {
      no[i][j] = node_cnt;
      if (i % 2 == 0)
        add_bi_edge(i, node_cnt, cnt[i][j]);
      else
        add_bi_edge(node_cnt, i, cnt[i][j]);
      node_cnt++;
    }
  }
  for (int k = 0; k < int(m); k++) {
    if (good[k][0] % 2 == 1) swap(good[k][0], good[k][1]);
    int i = good[k][0], j = good[k][1];
    int ii = 0, jj = 0;
    while (ii < sz[i] && jj < sz[j]) {
      if (d[i][ii] == d[j][jj])
        add_bi_edge(no[i][ii++], no[j][jj++], MAXE);
      else if (d[i][ii] < d[j][jj])
        ii++;
      else
        jj++;
    }
  }
  printf("%d\n", solve());
  return 0;
}
