#include <bits/stdc++.h>
using namespace std;
vector<int> ed[200000];
int a[20000], b[2000000], n, x, y, leftt[200000], m, l1[200000], r1[200000], v,
    used[200000], ans[200000];
bool dfs(int x) {
  if (used[x] == 1) return false;
  used[x] = 1;
  for (int i = 0; i < ed[x].size(); i++) {
    int to = ed[x][i];
    if (ans[to] == 0 || dfs(ans[to])) {
      ans[to] = x;
      return true;
    }
  }
  return false;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) {
    int x = a[i];
    l1[i] = v + 1;
    for (int j = 2; j <= 33000; j++) {
      while (x % j == 0) {
        v++;
        b[v] = j;
        x = x / j;
      }
    }
    if (x != 1) {
      v++;
      b[v] = x;
    }
    r1[i] = v;
    if (i % 2 == 1)
      for (int j = l1[i]; j <= r1[i]; j++) leftt[j] = 1;
  }
  for (int i = 1; i <= m; i++) {
    cin >> x >> y;
    if (x % 2 < y % 2) {
      int c = x;
      x = y;
      y = c;
    }
    for (int i1 = l1[x]; i1 <= r1[x]; i1++)
      for (int j1 = l1[y]; j1 <= r1[y]; j1++)
        if (b[i1] == b[j1]) ed[i1].push_back(j1);
  }
  for (int i = 1; i <= v; i++) {
    for (int j = 1; j <= v; j++) used[j] = 0;
    dfs(i);
  }
  int p = 0;
  for (int i = 1; i <= v; i++)
    if (ans[i] != 0) p++;
  cout << p << "\n";
  return 0;
}
