#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;
const int MAXM = 100 * 40;
const int INF = 1000000000;
int a[MAXN];
bool ok[MAXN][MAXN];
vector<int> P[MAXN];
vector<int> adj[MAXM];
int match[MAXM], l[MAXM];
bool visited[MAXM];
int n, m, nlist;
bool found;
void vuong(int u) {
  int v = a[u];
  for (int i = 2; (long long)(i)*i <= v; i++) {
    if (v % i == 0) {
      while (v % i == 0) {
        P[u].push_back(i);
        v /= i;
      }
    }
  }
  if (v > 1) P[u].push_back(v);
}
void init() {
  for (int i = 1; i <= n; i++) match[i] = 0;
  for (int i = 1; i <= m; i++) l[i] = i;
}
void DFS(int u) {
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (!visited[v]) {
      visited[v] = true;
      if (match[v] == 0)
        found = true;
      else
        DFS(match[v]);
      if (found) {
        match[v] = u;
        return;
      }
    }
  }
}
void matching() {
  int old = 0;
  nlist = m;
  do {
    old = nlist;
    for (int i = 1; i <= n; i++) visited[i] = false;
    for (int i = nlist; i >= 1; i--) {
      found = false;
      DFS(l[i]);
      if (found) {
        l[i] = l[nlist];
        nlist--;
      }
    }
  } while (old != nlist);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    ok[u][v] = ok[v][u] = true;
  }
  for (int i = 1; i <= n; i++) vuong(i);
  m = 0;
  int nn = 0;
  for (int i = 1; i <= n; i++) {
    if (i % 2 == 1) {
      nn = 0;
      for (int j = 1; j <= n; j++) {
        if (ok[i][j]) {
          for (int u = 0; u < P[i].size(); u++) {
            if (u > 0) nn -= P[j].size();
            m++;
            for (int v = 0; v < P[j].size(); v++) {
              nn++;
              if (P[i][u] == P[j][v]) adj[m].push_back(nn);
            }
          }
          m -= P[i].size();
        } else
          nn += P[j].size();
      }
      m += P[i].size();
    }
  }
  n = nn;
  init();
  matching();
  cout << m - nlist << endl;
}
