#include <bits/stdc++.h>
using namespace std;
vector<int> factors(long long n) {
  vector<int> ret;
  for (long long i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret.push_back(i);
      n /= i;
    }
  }
  if (n != 1) ret.push_back(n);
  return ret;
}
int n, m;
int n1, n2;
const int N = 5002;
vector<int> fac[N];
int vis[N], match[N];
int v[N];
int qtd[N];
vector<int> g[N];
int dfs(int x) {
  if (vis[x]) return 0;
  vis[x] = 1;
  for (int i = 0; i < g[x].size(); ++i) {
    int y = g[x][i];
    if (match[y] == -1 || dfs(match[y])) {
      match[y] = x;
      return 1;
    }
  }
  return 0;
}
int main() {
  n1 = n2 = 0;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", v + i);
    vector<int> foo = factors(v[i]);
    fac[i] = foo;
    if (i & 1) {
      qtd[i] = n1;
      n1 += foo.size();
    } else {
      qtd[i] = n2;
      n2 += foo.size();
    }
  }
  while (m--) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (b & 1) swap(a, b);
    for (int i = 0; i < fac[a].size(); ++i) {
      for (int j = 0; j < fac[b].size(); ++j) {
        if (fac[a][i] == fac[b][j]) {
          g[i + qtd[a]].push_back(j + qtd[b] + n1);
        }
      }
    }
  }
  int ans = 0;
  memset(match, -1, sizeof match);
  for (int i = 0; i < n1; ++i) {
    memset(vis, 0, sizeof vis);
    ans += dfs(i);
  }
  printf("%d\n", ans);
  return 0;
}
