#include <bits/stdc++.h>
using namespace std;
const int N = 100;
const int V = 100 * 50;
bool edge[V][V], nf[V];
int ans, cnt_v, n;
int from[V], start_v[N], value[V];
void ri() {
  int a, i, j, m, x1, x2;
  memset(from, 0xff, sizeof(from));
  memset(edge, false, sizeof(edge));
  cin >> n >> m;
  for (i = 0; i < n; i++) {
    start_v[i] = cnt_v;
    cin >> a;
    j = 2;
    while (a > 1) {
      for (; j * j <= a && a % j != 0; j++)
        ;
      if (a % j != 0) j = a;
      value[cnt_v++] = j;
      a /= j;
    }
  }
  start_v[n] = cnt_v;
  while (m--) {
    cin >> x1 >> x2;
    x1--;
    x2--;
    for (i = start_v[x1]; i < start_v[x1 + 1]; i++)
      for (j = start_v[x2]; j < start_v[x2 + 1]; j++) {
        edge[i][j] = value[i] == value[j];
        edge[j][i] = value[i] == value[j];
      }
  }
}
bool ok(int v1) {
  int temp, v2;
  nf[v1] = false;
  for (v2 = 0; v2 < cnt_v; v2++)
    if (edge[v1][v2] && nf[v2]) {
      nf[v2] = false;
      temp = from[v2];
      from[v2] = v1;
      if (temp == -1 || ok(temp)) return true;
      from[v2] = temp;
    }
  return false;
}
void solve() {
  int i, j;
  for (i = 0; i < n; i++) {
    if (i & 1) continue;
    for (j = start_v[i]; j < start_v[i + 1]; j++) {
      memset(nf, true, sizeof(nf));
      if (ok(j)) ans++;
    }
  }
}
void print() { cout << ans << endl; }
int main() {
  ri();
  solve();
  print();
  return 0;
}
