#include <bits/stdc++.h>
using namespace std;
int n, m, len;
vector<int> e[5555];
int visited[5555], parent[5555];
int arr[101];
pair<int, int> brr[101];
int good[101][101];
bool rec(int x) {
  if (visited[x] != 0) return false;
  visited[x] = 1;
  for (auto cur : e[x]) {
    if (parent[cur] == -1 || rec(parent[cur])) {
      parent[cur] = x;
      return true;
    }
  }
  return false;
}
int main() {
  int i, j, k, t, a, b;
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  vector<pair<int, int> > p1, p2;
  for (i = 0; i < n; i++) {
    cin >> a;
    for (j = 2; j <= 40000; j++) {
      while (a % j == 0) {
        if (i % 2)
          p1.push_back(pair<int, int>(j, i));
        else
          p2.push_back(pair<int, int>(j, i));
        a /= j;
      }
    }
    if (a > 1) {
      if (i % 2)
        p1.push_back(pair<int, int>(a, i));
      else
        p2.push_back(pair<int, int>(a, i));
    }
  }
  for (i = 0; i < m; i++) {
    cin >> a >> b;
    good[--a][--b] = 1;
    good[b][a] = 1;
  }
  for (i = 0; i < ((int)p1.size()); i++)
    for (j = 0; j < ((int)p2.size()); j++) {
      if (p1[i].first == p2[j].first and good[p1[i].second][p2[j].second])
        e[i].push_back(j);
    }
  memset(parent, -1, sizeof(parent));
  int ans = 0;
  for (i = 0; i < ((int)p1.size()); i++) {
    memset(visited, 0, sizeof(visited));
    if (rec(i)) ans++;
  }
  cout << ans << "\n";
  return 0;
}
