#include <bits/stdc++.h>
using namespace std;
int abs(int x) {
  if (x < 0) return -x;
  return x;
}
int addmod(int v1, int v2) {
  int v3 = v1 + v2;
  if (v3 >= 1000000007) v3 -= 1000000007;
  return v3;
}
int cc[100];
vector<int> v[105];
vector<int> cap[105];
int x[105], y[105], a[105];
int maxflow(int src, int sink, int n) {
  int ans = 0;
  while (true) {
    int prev[n + 5], dis[n + 5], nextpos[n + 5], prevpos[n + 5];
    for (int i = 0; i < n + 5; i++) dis[i] = 8944674;
    dis[src] = 0;
    queue<pair<int, pair<int, int> > > pq;
    pq.push(pair<int, pair<int, int> >(0, pair<int, int>(src, -1)));
    while (!pq.empty()) {
      pair<int, pair<int, int> > pp = pq.front();
      pq.pop();
      int cur = pp.second.first;
      for (int i = 0; i < v[cur].size(); i++) {
        int next = v[cur][i];
        if (pp.second.second == v[cur][i]) {
          prevpos[cur] = i;
        }
        if (cap[cur][i] > 0 && dis[next] == 8944674) {
          dis[next] = dis[cur] + 1;
          pq.push(
              pair<int, pair<int, int> >(dis[next], pair<int, int>(next, cur)));
          prev[next] = cur;
          nextpos[next] = i;
        }
      }
    }
    if (dis[sink] >= 8944674) break;
    int cur = sink;
    int minval = 8944674;
    while (cur != src) {
      minval = min(cap[prev[cur]][nextpos[cur]], minval);
      cur = prev[cur];
    }
    cur = sink;
    while (cur != src) {
      cap[prev[cur]][nextpos[cur]] -= minval;
      cap[cur][prevpos[cur]] += minval;
      cur = prev[cur];
    }
    ans += minval;
  }
  return ans;
}
int main() {
  set<int> ss;
  set<int>::iterator it;
  int n, m;
  scanf("%d", &n), scanf("%d", &m);
  for (int i = (0); i < (n); i++) {
    scanf("%d", &a[i]);
    int val = a[i];
    long long j = 2;
    while (j * j <= val) {
      while (val % j == 0) {
        ss.insert(j);
        val /= j;
      }
      j++;
    }
    if (val >= 2) {
      ss.insert(val);
    }
  }
  vector<int> primes;
  for ((it) = (ss).begin(); (it) != (ss).end(); (it)++) {
    primes.push_back(*it);
  }
  for (int i = (0); i < (m); i++) {
    scanf("%d", &x[i]), scanf("%d", &y[i]);
    x[i]--, y[i]--;
  }
  int ans = 0;
  for (int i = (0); i < (primes.size()); i++) {
    for (int j = (0); j < (n + 2); j++) v[j].clear(), cap[j].clear();
    for (int j = (0); j < (m); j++) {
      if (x[j] % 2 == 0) swap(x[j], y[j]);
      v[x[j]].push_back(y[j]);
      cap[x[j]].push_back(100001);
      v[y[j]].push_back(x[j]);
      cap[y[j]].push_back(0);
    }
    int s, t;
    s = n, t = n + 1;
    for (int j = (0); j < (n); j++) {
      int cc = 0;
      int val = a[j];
      while (val % primes[i] == 0) {
        cc++;
        val /= primes[i];
      }
      if (j % 2 == 1) {
        v[s].push_back(j);
        cap[s].push_back(cc);
        v[j].push_back(s);
        cap[j].push_back(0);
      } else {
        v[j].push_back(t);
        cap[j].push_back(cc);
        v[t].push_back(j);
        cap[t].push_back(0);
      }
    }
    ans += maxflow(s, t, n + 2);
  }
  cout << ans << endl;
  return 0;
}
