#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100, MAXM = 100, MAXEDGE = MAXN * 4 + MAXM * 2,
          oo = 1000000009;
int n, m, v[MAXN + 9], a[MAXEDGE + 9], b[MAXEDGE + 9], c[MAXEDGE + 9],
    val[MAXN + 9], ans, par[MAXN + 9];
vector<int> adj[MAXN + 9], vFac;
void CreateGraph() {
  for (int i = 1; i <= n; i++) {
    if (i % 2) {
      a[i + m] = n + 1;
      b[i + m] = i;
    } else {
      a[i + m] = i;
      b[i + m] = n + 2;
    }
  }
  m += n;
  for (int i = 1; i <= m; i++) {
    a[i + m] = b[i];
    b[i + m] = a[i];
    adj[a[i]].push_back(i);
    adj[b[i]].push_back(i + m);
  }
}
void Factorize(int x) {
  for (int i = 2; i <= x / i; i++) {
    if (!(x % i)) {
      vFac.push_back(i);
      while (!(x % i)) {
        x /= i;
      }
    }
  }
  if (x > 1) {
    vFac.push_back(x);
  }
}
int NFac(int x, int y) {
  int res = 0;
  while (!(x % y)) {
    x /= y;
    res++;
  }
  return res;
}
void InitGraph() {
  for (int i = 1; i <= m * 2; i++) {
    if (a[i] == n + 1) {
      c[i] = val[b[i]];
    } else if (b[i] == n + 2) {
      c[i] = val[a[i]];
    } else if (a[i] % 2 && !(b[i] % 2)) {
      c[i] = oo;
    } else {
      c[i] = 0;
    }
  }
}
int Rev(int x) {
  if (x > m) {
    return x - m;
  }
  return x + m;
}
int MaxFlow(int s, int t) {
  int res = 0;
  while (1) {
    fill(par, par + n + 3, 0);
    par[s] = -1;
    deque<int> dq;
    dq.push_back(s);
    while (!dq.empty()) {
      int x = dq.front();
      dq.pop_front();
      for (int i = 0; i < adj[x].size(); i++) {
        int id = adj[x][i];
        if (!par[b[id]] && c[id] > 0) {
          par[b[id]] = id;
          dq.push_back(b[id]);
        }
        if (par[t]) {
          break;
        }
      }
      if (par[t]) {
        break;
      }
    }
    if (!par[t]) {
      break;
    }
    int mn = oo;
    for (int i = t; i != s; i = a[par[i]]) {
      mn = min(mn, c[par[i]]);
    }
    for (int i = t; i != s; i = a[par[i]]) {
      c[par[i]] -= mn;
      c[Rev(par[i])] += mn;
    }
    res += mn;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> a[i] >> b[i];
    if (b[i] % 2) {
      swap(a[i], b[i]);
    }
  }
  CreateGraph();
  for (int i = 1; i <= n; i++) {
    Factorize(v[i]);
  }
  sort(vFac.begin(), vFac.end());
  vFac.erase(unique(vFac.begin(), vFac.end()), vFac.end());
  ans = 0;
  for (int iFac = 0; iFac < vFac.size(); iFac++) {
    int fac = vFac[iFac];
    for (int i = 1; i <= n; i++) {
      val[i] = NFac(v[i], fac);
    }
    InitGraph();
    ans += MaxFlow(n + 1, n + 2);
  }
  cout << ans << "\n";
  return 0;
}
