#include <bits/stdc++.h>
using namespace std;
const int N = 111;
int f[2 * N][2 * N], n, m, a[N], x[N * 2], y[N * 2], ans;
vector<char> used;
int cnt(int val, int div) {
  int res = 0;
  for (; val % div == 0; val /= div) res++;
  return res;
}
int dfs(int v = 0) {
  used[v] = true;
  if (v == 2 * n + 1) return true;
  for (int to = 0; to < 2 * n + 2; to++)
    if (!used[to] && f[v][to] > 0 && dfs(to)) {
      f[v][to]--;
      f[to][v]++;
      return true;
    }
  return false;
}
int calcFlow(int div) {
  for (int i = 0; i < 2 * N; i++)
    for (int j = 0; j < 2 * N; j++) f[i][j] = 0;
  for (int i = 0; i < n; i++) {
    f[0][i + 1] = cnt(a[i], div);
    f[n + i + 1][2 * n + 1] += cnt(a[i], div);
  }
  for (int i = 0; i < m; i++)
    f[x[i] + 1][n + y[i] + 1] = min(cnt(a[x[i]], div), cnt(a[y[i]], div));
  for (int res = 0;; res++) {
    used.assign(N * 2, false);
    if (!dfs()) return res;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  set<int> s;
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    a[i] = x;
    for (int j = 2; j * j <= x; j++)
      while (x % j == 0) {
        x /= j;
        s.insert(j);
      }
    if (x > 1) s.insert(x);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &x[i], &y[i]);
    x[i]--;
    y[i]--;
    x[m + i] = y[i];
    y[m + i] = x[i];
  }
  m *= 2;
  for (int div : s) ans += calcFlow(div) / 2;
  printf("%d", ans);
  return 0;
}
