#include <bits/stdc++.h>
using namespace std;
int vertex[5005];
bool graph[5005][5005];
int start[105], endd[105];
int match[5005];
int cnt;
bool help(int u, bool seen[]) {
  if (seen[u]) return 0;
  seen[u] = true;
  for (int i = 0; i < cnt; i++) {
    if (graph[u][i]) {
      if (match[i] == -1 || help(match[i], seen)) {
        match[i] = u;
        return 1;
      }
    }
  }
  return false;
}
int MAXmatch() {
  fill(match, match + 5005, -1);
  int res = 0;
  for (int i = 0; i < cnt; i++) {
    bool seen[5005];
    fill(seen, seen + 5005, 0);
    if (help(i, seen)) res++;
  }
  return res / 2;
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    start[i] = cnt;
    while (a % 2 == 0) {
      vertex[cnt++] = 2, a = a / 2;
    }
    for (int j = 3; j <= sqrt(a); j = j + 2) {
      while (a % j == 0) {
        vertex[cnt++] = j, a = a / j;
      }
    }
    if (a > 2) vertex[cnt++] = a;
    endd[i] = cnt - 1;
  }
  while (m--) {
    int u, v;
    cin >> u >> v;
    for (int i = start[u]; i <= endd[u]; i++) {
      for (int j = start[v]; j <= endd[v]; j++) {
        graph[i][j] = (vertex[i] == vertex[j]);
        graph[j][i] = (vertex[i] == vertex[j]);
      }
    }
  }
  cout << MAXmatch() << endl;
  return 0;
}
