#include <bits/stdc++.h>
using namespace std;
bool FindMatch(int i, const vector<vector<int> > &w, vector<int> &mr,
               vector<int> &mc, vector<int> &seen) {
  for (int j = 0; j < w[i].size(); j++) {
    if (w[i][j] && !seen[j]) {
      seen[j] = true;
      if (mc[j] < 0 || FindMatch(mc[j], w, mr, mc, seen)) {
        mr[i] = j;
        mc[j] = i;
        return true;
      }
    }
  }
  return false;
}
int BipartiteMatching(const vector<vector<int> > &w, vector<int> &mr,
                      vector<int> &mc) {
  mr = vector<int>(w.size(), -1);
  mc = vector<int>(w[0].size(), -1);
  int ct = 0;
  for (int i = 0; i < w.size(); i++) {
    vector<int> seen(w[0].size());
    if (FindMatch(i, w, mr, mc, seen)) ct++;
  }
  return ct;
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<vector<bool> > c(n, vector<bool>(n, false));
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    c[x][y] = c[y][x] = true;
  }
  vector<pair<int, int> > f[2];
  for (int i = 0; i < n; i++) {
    int rm = a[i];
    for (long long j = 2; j * j <= a[i]; j++) {
      while (rm % j == 0) {
        rm /= j;
        f[i % 2].push_back(make_pair(i, j));
      }
    }
    if (rm > 1) f[i % 2].push_back(make_pair(i, rm));
  }
  vector<vector<int> > w(f[0].size(), vector<int>(f[1].size(), 0));
  for (int i = 0; i < f[0].size(); i++)
    for (int j = 0; j < f[1].size(); j++) {
      if (f[0][i].second == f[1][j].second && c[f[0][i].first][f[1][j].first])
        w[i][j] = 1;
    }
  vector<int> mr, mc;
  int r = BipartiteMatching(w, mr, mc);
  cout << r << endl;
}
