#include <bits/stdc++.h>
int MOD = 1000000007;
using namespace std;
int i, j, n, m, k, p, q, l;
int x[1000], y[1000], a[1000], u[1000];
set<int> primes;
int g[200][200];
int dfs(int x, int fin, int w) {
  if (x == fin) return 1;
  u[x] = 1;
  int i;
  for (i = 0; i <= n + 1; i++)
    if (!u[i] && g[x][i] >= w && dfs(i, fin, w)) {
      g[x][i] -= w;
      g[i][x] += w;
      return 1;
    }
  return 0;
}
int main() {
  cin >> n >> m;
  for (i = 0; i < n; i++) cin >> a[i];
  for (i = 0; i < m; i++) {
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
    if (x[i] % 2 == 1) swap(x[i], y[i]);
  }
  for (i = 0; i < n; i++) {
    int x = a[i];
    for (j = 2; j * j <= x; j++) {
      if (x % j == 0) {
        primes.insert(j);
        while (x % j == 0) x /= j;
      }
    }
    if (x > 1) primes.insert(x);
  }
  set<int>::iterator it;
  int ans = 0;
  for (it = primes.begin(); it != primes.end(); it++) {
    int cur = *it;
    for (i = 0; i <= n + 1; i++)
      for (j = 0; j <= n + 1; j++) g[i][j] = 0;
    for (i = 0; i < n; i++) {
      int sum = 0;
      int x = a[i];
      while (x % cur == 0) {
        x /= cur;
        sum++;
      }
      if (i % 2 == 0)
        g[n][i] = sum;
      else
        g[i][n + 1] = sum;
    }
    for (i = 0; i < m; i++) g[x[i]][y[i]] = 1000;
    int w = 1000;
    while (w > 0) {
      for (i = 0; i <= n + 1; i++) u[i] = 0;
      if (dfs(n, n + 1, w))
        ans += w;
      else
        w /= 2;
    }
  }
  cout << ans << endl;
  return 0;
}
