#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
const int MAXN = 5000 + 10;
void solve(int tt) {}
int n, m;
int a[MAXN];
pair<int, int> pp[MAXN];
vector<int> get_primes(int x) {
  vector<int> res;
  for (int i = 2; i <= x / i; i++) {
    if (x % i == 0) res.push_back(i);
    while (x % i == 0) x /= i;
  }
  if (x > 1) res.push_back(x);
  return res;
}
int cnt(int x, int pr) {
  int res = 0;
  for (; x % pr == 0; x /= pr) res++;
  return res;
}
unordered_set<int> graph[MAXN];
int n1, n2;
int va[MAXN] = {}, vb[MAXN] = {};
int match[MAXN] = {0};
bool dfs(int i) {
  va[i] = 1;
  for (auto j : graph[i]) {
    if (vb[j]) continue;
    vb[j] = 1;
    if (match[j] < 0 || (!va[match[j]] && dfs(match[j]))) {
      match[j] = i;
      return true;
    }
  }
  return false;
}
int get_match() {
  fill(match, match + n2 + 1, -1);
  int res = 0;
  for (auto i = (1); i < (n1 + 1); i++) {
    fill(va, va + n1 + 1, 0);
    fill(vb, vb + n2 + 1, 0);
    res += dfs(i);
  }
  return res;
}
int main(int argc, char* argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n >> m;
  for (auto i = (1); i < (n + 1); i++) cin >> a[i];
  for (auto i = (1); i < (m + 1); i++) {
    cin >> pp[i].first >> pp[i].second;
    if (pp[i].first % 2 == 0) swap(pp[i].first, pp[i].second);
  }
  set<int> primes;
  for (auto i = (1); i < (n + 1); i++) {
    auto tmp = get_primes(a[i]);
    primes.insert((tmp).begin(), (tmp).end());
  }
  int res = 0;
  for (auto pr : primes) {
    vector<pair<int, int> > left, right;
    map<int, vector<int> > lmp, rmp;
    n1 = 0, n2 = 0;
    for (int i = 1; i <= n; i += 2) {
      int c = cnt(a[i], pr);
      if (c) {
        lmp[i] = {n1 + 1, n1 + c};
        n1 += c;
      }
    }
    for (int i = 2; i <= n; i += 2) {
      int c = cnt(a[i], pr);
      if (c) {
        rmp[i] = {n2 + 1, n2 + c};
        n2 += c;
      }
    }
    for (auto i = (0); i < (n1 + 1); i++) graph[i].clear();
    for (auto i = (1); i < (m + 1); i++) {
      int x = pp[i].first, y = pp[i].second;
      if (lmp.count(x) && rmp.count(y)) {
        for (auto ii = (lmp[x][0]); ii < (lmp[x][1] + 1); ii++) {
          for (auto jj = (rmp[y][0]); jj < (rmp[y][1] + 1); jj++) {
            graph[ii].insert(jj);
          }
        }
      }
    };
    ;
    ;
    ;
    ;
    ;
    res += get_match();
    ;
    ;
  }
  cout << res << '\n';
  return 0;
}
