#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const long long N = 100000;
long long n, m, s, t;
vector<pair<long long, long long> > nei[N + 1];
vector<long long> rv[N + 1];
void ae(long long x, long long y, long long z) {
  nei[x].push_back(make_pair(y, z)), nei[y].push_back(make_pair(x, 0));
  rv[x].push_back(nei[y].size() - 1), rv[y].push_back(nei[x].size() - 1);
}
long long dep[N + 1];
bool bfs() {
  memset(dep, -1, sizeof(dep));
  dep[s] = 0;
  queue<long long> q;
  q.push(s);
  while (q.size()) {
    long long x = q.front();
    q.pop();
    for (long long i = 0; i < nei[x].size(); i++) {
      long long y = nei[x][i].first, c = nei[x][i].second;
      if (c && !~dep[y]) dep[y] = dep[x] + 1, q.push(y);
    }
  }
  return ~dep[t];
}
long long now[N + 1];
long long dfs(long long x = s, long long flw = inf) {
  if (x == t || !flw) return flw;
  long long res = 0, tmp;
  for (long long &i = now[x]; i < nei[x].size(); i++) {
    long long y = nei[x][i].first, &c = nei[x][i].second;
    if (dep[y] == dep[x] + 1 && (tmp = dfs(y, min(flw, c)))) {
      res += tmp, flw -= tmp;
      c -= tmp, nei[y][rv[x][i]].second += tmp;
      if (!flw) break;
    }
  }
  return res;
}
long long dinic() {
  long long res = 0;
  while (bfs()) {
    memset(now, 0, sizeof(now));
    res += dfs();
  }
  return res;
}
map<long long, long long> id[N];
signed main() {
  cin >> n >> m;
  s = 1, t = 2;
  long long now = 2;
  for (long long i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    for (long long j = 2; j * j <= x; j++)
      if (x % j == 0) {
        long long cnt = 0;
        while (x % j == 0) cnt++, x /= j;
        id[i][j] = ++now;
        if (i & 1)
          ae(s, now, cnt);
        else
          ae(now, t, cnt);
      }
    if (x > 1) {
      id[i][x] = ++now;
      if (i & 1)
        ae(s, now, 1);
      else
        ae(now, t, 1);
    }
  }
  while (m--) {
    long long x, y;
    cin >> x >> y;
    if (y & 1) swap(x, y);
    for (map<long long, long long>::iterator i = id[x].begin();
         i != id[x].end(); i++) {
      if (id[y].find(i->first) != id[y].end())
        ae(i->second, id[y][i->first], inf);
    }
  }
  cout << dinic();
  return 0;
}
