#include <bits/stdc++.h>
using namespace std;
vector<int> ListAdj[4000];
vector<int> match, vis;
int CaN(int l) {
  if (vis[l]) return 0;
  vis[l] = 1;
  for (int i = 0; i < (int)ListAdj[l].size(); i++) {
    int r = ListAdj[l][i];
    if (match[r] == -1 || CaN(match[r])) {
      match[r] = l;
      return 1;
    }
  }
  return 0;
}
vector<int> fat(long long n) {
  vector<int> ret;
  for (long long i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      ret.push_back(i);
      n /= i;
    }
  }
  if (n != 1) ret.push_back(n);
  return ret;
}
int v[200];
vector<int> fatores[200];
int nPar[200];
int nImpar[200];
int main() {
  int n, m;
  while (cin >> n >> m) {
    int qPair = 0;
    int qOdd = 0;
    for (int i = 0; i < n; i++) {
      nPar[i] = qPair;
      nImpar[i] = qOdd;
      fatores[i].clear();
      scanf("%d", &v[i]);
      fatores[i] = fat(v[i]);
      if (i & 1)
        qOdd += fatores[i].size();
      else
        qPair += fatores[i].size();
    }
    for (int i = 0; i < m; ++i) {
      int a, b;
      scanf("%d %d", &a, &b);
      --a;
      --b;
      if (a & 1) swap(a, b);
      for (int j = 0; j < fatores[a].size(); ++j)
        for (int k = 0; k < fatores[b].size(); k++)
          if (fatores[a][j] == fatores[b][k]) {
            ListAdj[nPar[a] + j].push_back(qPair + nImpar[b] + k);
            ListAdj[qPair + nImpar[b] + k].push_back(nPar[a] + j);
          }
    }
    int ans = 0;
    match.assign(qPair + qOdd, -1);
    for (int i = 0; i < qPair; i++) {
      vis.assign(qPair, 0);
      ans += CaN(i);
    }
    cout << ans << endl;
  }
  return 0;
}
