#include <bits/stdc++.h>
using namespace std;
vector<int> primes;
set<int> usedPrimes;
bool isBad[100009];
void getPrimes() {
  for (int i = 2; i < 100000; i++) {
    if (isBad[i]) continue;
    primes.push_back(i);
    for (int j = 2; j * i < 100000; j++) {
      isBad[i * j] = true;
    }
  }
}
struct edge {
  int start;
  int end;
  int left;
  edge *rev;
};
bool used[2000];
int counter[2000];
vector<edge *> g[2000];
int n, m;
int dfs(int cur, int mini) {
  used[cur] = true;
  if (cur == n + 1) return mini;
  if (mini == 0) return 0;
  int deeper = 0;
  for (; counter[cur] < g[cur].size(); counter[cur]++) {
    if (g[cur][counter[cur]]->left == 0 || used[g[cur][counter[cur]]->end])
      continue;
    deeper =
        dfs(g[cur][counter[cur]]->end, min(mini, g[cur][counter[cur]]->left));
    g[cur][counter[cur]]->left -= deeper;
    g[cur][counter[cur]]->rev->left += deeper;
    if (deeper != 0) return deeper;
  }
  return deeper;
}
int getAns() {
  int ans = 0;
  int cur = 0;
  for (int i = 0; i < 200; i++) {
    used[i] = false;
    counter[i] = 0;
  }
  used[0] = true;
  while ((cur = dfs(0, 2000000000)) != 0) {
    ans += cur;
    for (int i = 0; i < 200; i++) {
      used[i] = false;
      counter[i] = 0;
    }
    used[0] = true;
  }
  return ans;
}
int main() {
  getPrimes();
  cin >> n >> m;
  int arr[120];
  pair<int, int> pairs[200];
  for (int i = 0; i < n; i++) cin >> arr[i];
  for (int i = 0; i < m; i++) cin >> pairs[i].first >> pairs[i].second;
  for (int i = 0; i < m; i++)
    if (pairs[i].first % 2 == 0) swap(pairs[i].first, pairs[i].second);
  for (int i = 0; i < n; i++) {
    int cur = arr[i];
    for (int j = 0; j < primes.size(); j++) {
      if (cur % primes[j] == 0 &&
          usedPrimes.find(primes[j]) == usedPrimes.end()) {
        usedPrimes.insert(primes[j]);
      }
      while (cur % primes[j] == 0) {
        cur /= primes[j];
      }
    }
    if (cur > 1 && usedPrimes.find(cur) == usedPrimes.end()) {
      usedPrimes.insert(cur);
      primes.push_back(cur);
    }
  }
  set<int>::iterator it = usedPrimes.begin();
  int getCount[200];
  int ans = 0;
  for (; it != usedPrimes.end(); it++) {
    for (int i = 0; i < 200; i++) getCount[i] = 0;
    for (int i = 0; i < 200; i++) g[i].clear();
    int p = *it;
    for (int i = 0; i < n; i++) {
      int cur = arr[i];
      while (cur % p == 0) {
        cur /= p;
        getCount[i]++;
      }
    }
    for (int i = 0; i < m; i++) {
      edge *e1 = new edge;
      edge *e2 = new edge;
      int sz = 0;
      int x = arr[pairs[i].first - 1];
      int y = arr[pairs[i].second - 1];
      while (x % p == 0 && y % p == 0) {
        sz++;
        x /= p;
        y /= p;
      }
      e1->start = pairs[i].first;
      e1->end = pairs[i].second;
      e1->left = sz;
      e2->start = e1->end;
      e2->end = e1->start;
      e2->left = 0;
      e1->rev = e2;
      e2->rev = e1;
      g[pairs[i].first].push_back(e1);
      g[pairs[i].second].push_back(e2);
    }
    for (int i = 0; i < n; i += 2) {
      edge *e1 = new edge;
      edge *e2 = new edge;
      e1->start = 0;
      e1->end = i + 1;
      e1->left = getCount[i];
      e2->start = e1->end;
      e2->end = e1->start;
      e2->left = 0;
      e1->rev = e2;
      e2->rev = e1;
      g[0].push_back(e1);
      g[i + 1].push_back(e2);
    }
    for (int i = 1; i < n; i += 2) {
      edge *e1 = new edge;
      edge *e2 = new edge;
      e1->start = i + 1;
      e1->end = n + 1;
      e1->left = getCount[i];
      e2->start = e1->end;
      e2->end = e1->start;
      e2->left = 0;
      e1->rev = e2;
      e2->rev = e1;
      g[i + 1].push_back(e1);
      g[n + 1].push_back(e2);
    }
    ans += getAns();
  }
  cout << ans << endl;
  return 0;
}
