#include <bits/stdc++.h>
using namespace std;
struct node {
  int v, c;
  node *opp, *next;
} Map[500];
node *List[110];
int d[110], vd[110];
int e, n;
int a[110], p1[110], p2[110], N, M;
bool b[100000 + 10];
int prime[100000 + 10], Nprime = 0;
void addedge(int i, int j, int c) {
  Map[++e].v = j;
  Map[e].c = c;
  Map[e].opp = &Map[e + 1];
  Map[e].next = List[i];
  List[i] = &Map[e];
  Map[++e].v = i;
  Map[e].c = 0;
  Map[e].opp = &Map[e - 1];
  Map[e].next = List[j];
  List[j] = &Map[e];
}
int dfs(int i, int flow) {
  int j, temp, ff = 0;
  node *u;
  if (i == n) return (flow);
  u = List[i];
  while (u != NULL) {
    j = u->v;
    if (u->c > 0 && d[i] == d[j] + 1) {
      temp = dfs(j, min(u->c, flow - ff));
      u->c = u->c - temp;
      u->opp->c = u->opp->c + temp;
      ff += temp;
      if (ff == flow) return (flow);
    }
    u = u->next;
  }
  if (d[1] >= n) return (ff);
  vd[d[i]]--;
  if (vd[d[i]] == 0) d[1] = n;
  d[i]++;
  vd[d[i]]++;
  return (ff);
}
void getprime() {
  for (int i = 2; i <= 100000; i++) {
    if (!b[i]) {
      prime[++Nprime] = i;
      for (int j = i + i; j <= 100000; j += i) b[j] = true;
    }
  }
}
int solve(int k) {
  e = 0;
  for (int i = 0; i < 110; i++) List[i] = NULL;
  for (int i = (1); i <= (M); ++i) {
    int t1 = a[p1[i]], t2 = a[p2[i]];
    int count = 0;
    while (t1 % k == 0 && t2 % k == 0) {
      t1 /= k;
      t2 /= k;
      count++;
    }
    if (p1[i] % 2 == 1)
      addedge(p1[i] + 1, p2[i] + 1, count);
    else
      addedge(p2[i] + 1, p1[i] + 1, count);
  }
  for (int i = (1); i <= (N); ++i) {
    int count = 0;
    while (a[i] % k == 0) {
      a[i] /= k;
      count++;
    }
    if (i % 2 == 1)
      addedge(1, i + 1, count);
    else
      addedge(i + 1, N + 2, count);
  }
  n = N + 2;
  memset(d, 0, sizeof(d));
  memset(vd, 0, sizeof(vd));
  vd[0] = n;
  int maxflow = 0;
  while (d[1] <= n - 1) maxflow = maxflow + dfs(1, 100000000);
  return maxflow;
}
int main() {
  getprime();
  scanf("%d%d", &N, &M);
  for (int i = (1); i <= (N); ++i) scanf("%d", a + i);
  for (int i = (1); i <= (M); ++i) scanf("%d%d", p1 + i, p2 + i);
  int ans = 0;
  for (int i = (1); i <= (Nprime); ++i) ans += solve(prime[i]);
  for (int i = (1); i <= (N); ++i)
    if (a[i] > 1) ans += solve(a[i]);
  printf("%d\n", ans);
  return 0;
}
