#include <bits/stdc++.h>
using namespace std;
const int MOD(1000000007);
const int INF((1 << 30) - 1);
const int MAXN(1005);
vector<int> prime;
int p[35000], f[MAXN][MAXN], a[MAXN], prv[MAXN], visited[MAXN], st[MAXN];
vector<pair<int, int> > g[MAXN];
bool dfs(int source, int sink, int num) {
  for (int i = 0; i < num; i++) visited[i] = false;
  int top = 0;
  st[top++] = source;
  visited[source] = true;
  while (top > 0) {
    int node = st[--top];
    if (node == sink) return true;
    for (int i = 0; i < num; i++) {
      if (!visited[i] && f[node][i] > 0) {
        st[top++] = i;
        visited[i] = true;
        prv[i] = node;
      }
    }
  }
  return false;
}
int maxflow(int source, int sink, int num) {
  int flow = 0;
  while (dfs(source, sink, num)) {
    int k = INF;
    for (int i = sink; i != source; i = prv[i]) k = min(k, f[prv[i]][i]);
    for (int i = sink; i != source; i = prv[i]) {
      f[prv[i]][i] -= k;
      f[i][prv[i]] += k;
    }
    flow += k;
  }
  return flow;
}
int main() {
  for (int i = 2; i <= 31700; i++) {
    if (!p[i]) {
      prime.push_back(i);
      for (int j = i * i; j <= 31700; j += i) p[j] = 1;
    }
  }
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  int node = 2;
  for (int i = 1; i <= n; i++) {
    int num = a[i];
    for (int j = 0; j < prime.size(); j++) {
      if (prime[j] > num) break;
      if (num % prime[j] == 0) {
        int cnt = 0;
        while (num % prime[j] == 0) {
          cnt++;
          num /= prime[j];
        }
        g[i].push_back(pair<int, int>(node, prime[j]));
        if (i % 2)
          f[0][node] = cnt;
        else
          f[node][1] = cnt;
        node++;
      }
    }
    if (num > 1) {
      g[i].push_back(pair<int, int>(node, num));
      if (i % 2)
        f[0][node] = 1;
      else
        f[node][1] = 1;
      node++;
    }
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    int k1 = 0, k2 = 0, num1 = a[x], num2 = a[y];
    for (int j = 0; j < prime.size(); j++) {
      if (prime[j] > min(a[x], a[y])) break;
      if (a[x] % prime[j] == 0 && a[y] % prime[j] == 0) {
        while (num1 % prime[j] == 0) num1 /= prime[j];
        while (num2 % prime[j] == 0) num2 /= prime[j];
        while (g[x][k1].second != prime[j]) k1++;
        while (g[y][k2].second != prime[j]) k2++;
        int u = g[x][k1].first;
        int v = g[y][k2].first;
        if (x % 2)
          f[u][v] = INF;
        else
          f[v][u] = INF;
      }
    }
    if (num1 > 1 && num1 == num2) {
      while (g[x][k1].second != num1) k1++;
      while (g[y][k2].second != num2) k2++;
      int u = g[x][k1].first;
      int v = g[y][k2].first;
      if (x % 2)
        f[u][v] = INF;
      else
        f[v][u] = INF;
    }
  }
  printf("%d", maxflow(0, 1, node));
}
