#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T modinv(T a, T n) {
  T i = n, v = 0, d = 1;
  while (a > 0) {
    T t = i / a, x = a;
    a = i % x;
    i = x;
    x = d;
    d = v - t * x;
    v = x;
  }
  return (v + n) % n;
}
long long modpow(long long n, long long k, long long mod) {
  long long ans = 1;
  while (k > 0) {
    if (k & 1) ans = (ans * n) % mod;
    k >>= 1;
    n = (n * n) % mod;
  }
  return ans % mod;
}
template <class T>
string str(T Number) {
  string Result;
  ostringstream convert;
  convert << Number;
  Result = convert.str();
  return Result;
}
int StringToNumber(const string &Text) {
  istringstream ss(Text);
  int result;
  return ss >> result ? result : 0;
}
template <class T>
inline vector<pair<T, int> > FACTORISE(T n) {
  vector<pair<T, int> > R;
  for (T i = 2; n > 1;) {
    if (n % i == 0) {
      int C = 0;
      for (; n % i == 0; C++, n /= i)
        ;
      R.push_back(make_pair(i, C));
    }
    i++;
    if (i > n / i) i = n;
  }
  if (n > 1) R.push_back(make_pair(n, 1));
  return R;
}
template <class T>
inline T TOTIENT(T n) {
  vector<pair<T, int> > R = FACTORISE(n);
  T r = n;
  for (int i = 0; i < R.size(); i++) r = r / R[i].first * (R[i].first - 1);
  return r;
}
template <class T>
inline T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
double rnd(float d) { return floor(d + 0.49); }
int edge[3300][3300], Pairs[3300][3300];
int match[3300];
bool seen[3300];
vector<pair<int, int> > groups;
bool bfs(int v) {
  seen[v] = 1;
  for (int i = 0; i < ((int)(groups).size()); i++) {
    if (edge[v][i] && !seen[i]) {
      seen[i] = 1;
      if (match[i] == -1 || bfs(match[i])) {
        match[v] = i;
        match[i] = v;
        return true;
      }
    }
  }
  seen[v] = 0;
  return false;
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> A(n);
  for (int i = 0; i < n; i++) {
    cin >> A[i];
    int x = A[i];
    for (int j = 2; j * j <= A[i]; j++) {
      if (j > x) break;
      while (x % j == 0) {
        x = x / j;
        groups.push_back(make_pair(j, i));
      }
    }
    if (x > 1) groups.push_back(make_pair(x, i));
  }
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    Pairs[a][b] = 1, Pairs[b][a] = 1;
  }
  memset(edge, 0, sizeof(edge));
  for (int i = 0; i < ((int)(groups).size()); i++)
    for (int j = i + 1; j < ((int)(groups).size()); j++) {
      if (Pairs[groups[i].second][groups[j].second] &&
          groups[i].first == groups[j].first)
        edge[i][j] = 1, edge[j][i] = 1;
    }
  memset(match, -1, sizeof(match));
  int matchings = 0;
  for (int i = 0; i < ((int)(groups).size()); i++) {
    if (match[i] != -1) continue;
    memset(seen, false, sizeof(seen));
    if (bfs(i)) matchings++;
  }
  cout << matchings << endl;
  return 0;
}
