#include <bits/stdc++.h>
using namespace std;
const int M = 4 * 10000;
int v[M + 10];
vector<int> l;
int a[200], n, m, J, E;
vector<int> g[200];
pair<int, int> e[300];
int f[300], w[300];
int s, t;
int mark[200];
int f1(int c, int a, int b = -1) {
  if (a % c) return 0;
  if (~b && b % c) return 0;
  return f1(c, a / c, b / c) + 1;
}
int dfs(int v, int fl) {
  if (v == t || !fl) return fl;
  if (mark[v]++) return 0;
  for (int i = 0; i < g[v].size(); i++) {
    int I = g[v][i];
    if (v == e[I].first) {
      int u = e[I].second;
      int z = w[I] - f[I];
      int x = dfs(u, min(fl, z));
      if (!x) continue;
      f[I] += x;
      return x;
    } else {
      int u = e[I].first;
      int z = f[I];
      int x = dfs(u, min(fl, z));
      if (!x) continue;
      f[I] -= x;
      return x;
    }
  }
  return 0;
}
void f2(int A) {
  if (A == 1) return;
  memset(f, 0, sizeof f);
  for (int j = 0; j < m; j++) w[j] = f1(A, a[e[j].first], a[e[j].second]);
  for (int j = 0; j < n; j++) w[j + m] = f1(A, a[j]);
  int x = 0;
  do {
    J += x;
    memset(mark, 0, sizeof mark);
  } while (x = dfs(s, 100));
  for (int i = 0; i < n; i++)
    while ((a[i] % A) == 0) a[i] /= A;
}
void adde(int x, int y) {
  e[E].first = x;
  e[E].second = y;
  g[x].push_back(E);
  g[y].push_back(E);
  E++;
}
int main() {
  for (int i = 2; i <= M; i++) {
    if (v[i]) continue;
    for (int j = i; j <= M; j += i) v[j] = 1;
    l.push_back(i);
  }
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    if (y % 2) swap(x, y);
    adde(x, y);
  }
  s = n;
  t = n + 1;
  for (int i = 0; i < n; i++)
    if (i % 2)
      adde(s, i);
    else
      adde(i, t);
  for (int i = 0; i < l.size(); i++) f2(l[i]);
  for (int i = 0; i < n; i++) f2(a[i]);
  cout << J << endl;
}
