#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 3000 + 10;
const long long K = 100000;
const long long base = 1000000000;
const long long base_digits = 9;
long long cnt, n, m, ans, a[MAXN], bas[MAXN][2], P[MAXN], match[MAXN];
bool vis[MAXN], G[MAXN][MAXN];
vector<int> adj[MAXN];
bool dfs(long long v) {
  vis[v] = 1;
  for (long long i = 0; i < (int((adj[v]).size())); i++)
    if (match[adj[v][i]] == 0) {
      match[v] = adj[v][i];
      match[adj[v][i]] = v;
      return 1;
    }
  for (long long i = 0; i < (int((adj[v]).size())); i++) {
    long long u = match[adj[v][i]];
    if (!vis[u] && dfs(u)) {
      match[v] = adj[v][i];
      match[adj[v][i]] = v;
      return 1;
    }
  }
  return 0;
}
void make(long long id) {
  bas[id][0] = cnt + 1;
  long long a0 = a[id];
  for (long long i = 2; i * i <= a[id]; i++)
    while (a0 % i == 0) {
      P[++cnt] = i;
      a0 /= i;
    }
  if (a0 > 1) P[++cnt] = a0;
  bas[id][1] = cnt;
}
int main() {
  cin >> n >> m;
  for (long long i = 0; i < n; i++) cin >> a[i];
  for (long long i = 0; i < m; i++) {
    long long x, y;
    cin >> x >> y;
    x--;
    y--;
    G[x][y] = G[y][x] = 1;
  }
  for (long long i = 0; i < n; i++) make(i);
  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < i; j++)
      if (G[i][j])
        for (long long s0 = bas[i][0]; s0 <= bas[i][1]; s0++)
          for (long long s1 = bas[j][0]; s1 <= bas[j][1]; s1++)
            if (P[s0] == P[s1]) {
              adj[s0].push_back(s1);
              adj[s1].push_back(s0);
            }
  for (long long i = 1; i <= cnt; i++)
    if (match[i] == 0 && dfs(i)) {
      ans++;
      memset(vis, 0, sizeof vis);
    }
  cout << ans;
  return 0;
}
