#include <bits/stdc++.h>
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
using namespace std;
int a[MAXN], st[MAXN], en[MAXN], vis[MAXN][2], match[MAXN][2];
vector<int> adj[MAXN][2];
vector<int> l, r;
int dfs(int u, int fl) {
  for (int v : adj[u][fl]) {
    if (vis[v][fl ^ 1]) continue;
    vis[v][fl ^ 1] = 1;
    if (match[v][fl ^ 1] == -1 || dfs(match[v][fl ^ 1], fl)) {
      match[v][fl ^ 1] = u;
      return 1;
    }
  }
  return 0;
}
int main() {
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < MAXN; j++) match[j][i] = -1;
  int n, m;
  scanf("%d", &(n)), scanf("%d", &(m));
  for (int i = 0; i < n; i++) {
    scanf("%d", &(a[i]));
    int x = a[i];
    if (i & 1)
      st[i] = l.size();
    else
      st[i] = r.size();
    for (int j = 2; j * j <= a[i]; j++) {
      while (x % j == 0) {
        x /= j;
        if (i & 1)
          l.push_back(j);
        else
          r.push_back(j);
      }
    }
    if (x > 1) {
      if (i & 1)
        l.push_back(x);
      else
        r.push_back(x);
    }
    if (i & 1)
      en[i] = l.size();
    else
      en[i] = r.size();
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d", &(x)), scanf("%d", &(y));
    if (x & 1) swap(x, y);
    for (int j = st[x - 1]; j < en[x - 1]; j++) {
      for (int k = st[y - 1]; k < en[y - 1]; k++) {
        if (l[j] != r[k]) continue;
        adj[j][0].push_back(k);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < l.size(); i++) {
    memset(vis, 0, sizeof vis);
    if (match[i][0] == -1) ans += dfs(i, 0);
  }
  printf("%d\n", (ans));
  return 0;
}
