#include <bits/stdc++.h>
using namespace std;
vector<int> ps;
bool vis[300009];
void init() {
  memset(vis, 0, sizeof(vis));
  ;
  for (int i = 2; i <= 2e5; i++)
    if (!vis[i])
      for (int j = i + i; j <= 2e5; j += i) vis[j] = 1;
  for (int i = 2; i * i <= 1e9; i++)
    if (!vis[i]) ps.push_back(i);
}
int a[102], n, m, ans = 0;
pair<int, int> pa[102];
const int Ni = 210;
const int MAX = 1 << 26;
struct Edge {
  int u, v, c;
  int next;
} edge[20 * Ni];
int edn;
int p[Ni];
int d[Ni];
int sp, tp;
void addedge(int u, int v, int c) {
  edge[edn].u = u;
  edge[edn].v = v;
  edge[edn].c = c;
  edge[edn].next = p[u];
  p[u] = edn++;
  edge[edn].u = v;
  edge[edn].v = u;
  edge[edn].c = 0;
  edge[edn].next = p[v];
  p[v] = edn++;
}
int bfs() {
  queue<int> q;
  memset(d, -1, sizeof(d));
  d[sp] = 0;
  q.push(sp);
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = p[cur]; i != -1; i = edge[i].next) {
      int u = edge[i].v;
      if (d[u] == -1 && edge[i].c > 0) {
        d[u] = d[cur] + 1;
        q.push(u);
      }
    }
  }
  return d[tp] != -1;
}
int dfs(int a, int b) {
  int r = 0;
  if (a == tp) return b;
  for (int i = p[a]; i != -1 && r < b; i = edge[i].next) {
    int u = edge[i].v;
    if (edge[i].c > 0 && d[u] == d[a] + 1) {
      int x = min(edge[i].c, b - r);
      x = dfs(u, x);
      r += x;
      edge[i].c -= x;
      edge[i ^ 1].c += x;
    }
  }
  if (!r) d[a] = -2;
  return r;
}
int dinic(int sp, int tp) {
  int total = 0, t;
  while (bfs()) {
    while (t = dfs(sp, MAX)) total += t;
  }
  return total;
}
void cal(int v) {
  for (int j = (1); j <= (n); j++) {
    int cnt = 0, x = a[j];
    while (x % v == 0) cnt++, x /= v;
    if (j & 1)
      addedge(sp, j, cnt);
    else
      addedge(j, tp, cnt);
  }
  for (int j = 0; j < (m); j++)
    if (a[pa[j].first] % v == 0 && a[pa[j].second] % v == 0) {
      if (pa[j].first & 1)
        addedge(pa[j].first, pa[j].second, 1000000);
      else
        addedge(pa[j].second, pa[j].first, 1000000);
    }
  int tmp = dinic(sp, tp);
  ans += tmp;
  for (int i = (1); i <= (n); i++)
    while (a[i] % v == 0) a[i] /= v;
}
int main() {
  init();
  cin >> n;
  cin >> m;
  for (int i = (1); i <= (n); i++) cin >> a[i];
  for (int i = 0; i < (m); i++) cin >> pa[i].first >> pa[i].second;
  for (int i = 0; i < (ps.size()); i++) {
    edn = 0;
    sp = 0;
    tp = n + 1;
    memset(p, -1, sizeof(p));
    ;
    memset(edge, -1, sizeof(edge));
    ;
    int v = ps[i];
    cal(v);
  }
  for (int i = (1); i <= (n); i++) {
    int v = a[i];
    if (v == 1) continue;
    edn = 0;
    sp = 0;
    tp = n + 1;
    memset(p, -1, sizeof(p));
    ;
    memset(edge, -1, sizeof(edge));
    ;
    cal(v);
  }
  cout << ans << endl;
}
