#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, oo = 1e8;
int notp[maxn + 10], mu[maxn + 10], phi[maxn + 10], smu[maxn + 10];
vector<int> prime;
void getprimes_linear() {
  memset(notp, 0, sizeof(notp));
  notp[1] = phi[1] = mu[1] = 1;
  prime.clear();
  for (int i = 2; i <= maxn; i++) {
    if (!notp[i]) {
      prime.push_back(i);
      phi[i] = i - 1;
      mu[i] = -1;
    }
    for (int j = 0; j < (int)prime.size() && prime[j] * i <= maxn; j++) {
      notp[i * prime[j]] = 1;
      if (i % prime[j]) {
        phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        mu[i * prime[j]] = -mu[i];
      } else {
        phi[i * prime[j]] = phi[i] * prime[j];
        mu[i * prime[j]] = 0;
        break;
      }
    }
  }
  smu[0] = 0;
  for (int i = 1; i <= maxn; i++) smu[i] = smu[i - 1] + mu[i];
}
struct edge {
  int y, c, next;
  edge() {}
  edge(int y_, int c_, int n_) { y = y_, c = c_, next = n_; }
} e[900005];
int head[20005];
int nn, mm;
int d[20005], cont[20005], q[20005];
int pre[20005], cur[20005];
bool vis[20005];
void bfs(int s) {
  int x, to, tail = 1, front = 0;
  for (int i = 1; i <= nn; i++)
    vis[i] = cont[i] = 0, cur[i] = head[i], d[i] = 0x3fffffff;
  d[s] = 0;
  cont[0] = 1;
  q[0] = s;
  vis[s] = 1;
  while (front < tail)
    for (int i = head[x = q[front++]]; i != -1; i = e[i].next)
      if (!vis[to = e[i].y] && e[i ^ 1].c) {
        d[to] = d[x] + 1;
        vis[to] = 1;
        q[tail++] = to;
        cont[d[to]]++;
      }
}
int SAP(int s, int t) {
  if (s == t) return 0x7fffffff;
  bfs(t);
  pre[s] = -1;
  int ans = 0, x = s, y, len = 0, flow, back;
  while (d[s] < nn) {
    y = -1;
    for (int i = cur[x]; i != -1; i = e[i].next)
      if (e[i].c && d[x] == d[e[i].y] + 1) {
        y = e[i].y;
        cur[x] = i;
        break;
      }
    if (y != -1) {
      pre[y] = x;
      x = y;
      if (x == t) {
        flow = 0x3fffffff;
        for (y = pre[y]; y != -1; y = pre[y])
          if (flow >= e[cur[y]].c) flow = e[cur[y]].c, back = y;
        for (x = pre[x]; x != -1; x = pre[x])
          e[cur[x] ^ 1].c += flow, e[cur[x]].c -= flow;
        ans += flow;
        x = back;
      }
    } else {
      y = nn;
      for (int i = head[x]; i != -1; i = e[i].next)
        if (e[i].c && y > d[e[i].y]) y = d[e[i].y], cur[x] = i;
      cont[d[x]]--;
      if (cont[d[x]] == 0) break;
      cont[d[x] = y + 1]++;
      if (x != s) x = pre[x];
    }
  }
  return ans;
}
void add(int x, int y, int c) {
  e[mm] = edge(y, c, head[x]);
  head[x] = mm++;
  e[mm] = edge(x, 0, head[y]);
  head[y] = mm++;
}
int a[1000], used[1000], u[1000], v[1000], pp[1000][100];
set<int> st;
vector<pair<int, int> > fc[1000];
int main() {
  getprimes_linear();
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n + 1; i++) scanf("%d", a + i);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", u + i, v + i);
    used[u[i]] = 1;
    used[v[i]] = 1;
  }
  int ttt = 2 * n + 1;
  int cnt;
  for (int i = 1; i < n + 1; i++) {
    if (!used[i]) continue;
    int x = a[i];
    for (int j = 0; j < (int)prime.size(); j++) {
      cnt = 0;
      for (; x % prime[j] == 0; x /= prime[j], cnt++)
        ;
      if (cnt) fc[i].push_back(make_pair(prime[j], cnt));
      if (x == 1) break;
    }
    if (x > 1) fc[i].push_back(make_pair(x, 1));
  }
  mm = 0;
  memset(head, -1, sizeof(head));
  for (int i = 1; i < n + 1; i++) {
    if (!used[i]) continue;
    for (int j = 0; j < (int)fc[i].size(); j++) {
      pp[i][j] = ttt;
      if (i % 2)
        add(ttt, n + i, fc[i][j].second);
      else
        add(i, ttt, fc[i][j].second);
      ttt++;
    }
  }
  for (int i = 0; i < m; i++) {
    if (u[i] % 2 == 1) swap(u[i], v[i]);
    for (int j = 0; j < (int)fc[u[i]].size(); j++)
      for (int k = 0; k < (int)fc[v[i]].size(); k++)
        if (fc[u[i]][j].first == fc[v[i]][k].first)
          add(pp[u[i]][j], pp[v[i]][k], oo);
  }
  int ST = ttt, ED = ttt + 1;
  nn = ttt + 1;
  for (int i = 1; i < n + 1; i++) {
    if (i % 2)
      add(n + i, ED, oo);
    else
      add(ST, i, oo);
  }
  printf("%d\n", SAP(ST, ED));
  return 0;
}
