#include <bits/stdc++.h>
using namespace std;
int a[101];
vector<pair<int, int> > factors[101];
vector<int> ADJ[100000];
bool seen[100000];
int match[100000];
int COUNT = 0;
bool bpm(int u) {
  for (int i = 0; i < ADJ[u].size(); i++) {
    int v = ADJ[u][i];
    if (!seen[v]) {
      seen[v] = true;
      if (match[v] == -1 || bpm(match[v])) {
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
  }
  return false;
}
int maxBPM() {
  memset(match, -1, sizeof(match));
  int result = 0;
  for (int u = 0; u < COUNT; u++) {
    if (match[u] == -1) {
      memset(seen, 0, sizeof(seen));
      if (bpm(u)) result++;
    }
  }
  return result;
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j * j <= a[i]; j++) {
      if (a[i] % j) continue;
      while (a[i] % j == 0) {
        factors[i].push_back(make_pair(j, COUNT));
        COUNT++;
        a[i] /= j;
      }
    }
    if (a[i] > 1) {
      factors[i].push_back(make_pair(a[i], COUNT));
      COUNT++;
    }
  }
  for (int _i = 1; _i <= m; _i++) {
    int ik, jk;
    cin >> ik >> jk;
    for (int i = 0; i < factors[ik].size(); i++) {
      for (int j = 0; j < factors[jk].size(); j++) {
        if (factors[ik][i].first == factors[jk][j].first) {
          ADJ[factors[ik][i].second].push_back(factors[jk][j].second);
          ADJ[factors[jk][j].second].push_back(factors[ik][i].second);
        }
      }
    }
  }
  cout << maxBPM() << endl;
  return 0;
}
