#include <bits/stdc++.h>
using namespace std;
vector<int> v[1000000];
vector<int> fac[200];
int sum[200];
int pr[1000000];
bool visit[1000000];
int N, M;
int A[200];
bool find(int x) {
  visit[x] = true;
  for (int vi = 0; vi < v[x].size(); vi++) {
    int p = pr[v[x][vi]];
    if (p == x) continue;
    if ((!p) || (!visit[p] && find(p))) {
      pr[v[x][vi]] = x;
      pr[x] = v[x][vi];
      return true;
    }
  }
  return false;
}
int bipartite() {
  int cnt = 0;
  for (int Ni = 1; Ni <= N; Ni += 2)
    for (int vi = 0; vi < fac[Ni].size(); vi++)
      if (!pr[sum[Ni] + vi]) {
        if (find(sum[Ni] + vi)) cnt++;
        fill(visit, visit + sum[N + 1], false);
      }
  return cnt;
}
int main() {
  scanf("%d %d", &N, &M);
  for (int Ni = 1; Ni <= N; Ni++) {
    scanf("%d", &A[Ni]);
    int x = A[Ni];
    for (int i = 2; i * i <= x; i++)
      while (x % i == 0) {
        x /= i;
        fac[Ni].push_back(i);
      }
    if (x != 1) fac[Ni].push_back(x);
  }
  for (int Ni = 1; Ni <= N + 1; Ni++) {
    if (Ni == 1)
      sum[Ni] = 1;
    else
      sum[Ni] = sum[Ni - 1] + fac[Ni - 1].size();
  }
  for (int Mi = 1; Mi <= M; Mi++) {
    int a, b;
    scanf("%d %d", &a, &b);
    vector<int> &va = fac[a];
    vector<int> &vb = fac[b];
    for (int ai = 0; ai < va.size(); ai++)
      for (int bi = 0; bi < vb.size(); bi++)
        if (va[ai] == vb[bi]) {
          v[sum[a] + ai].push_back(sum[b] + bi);
          v[sum[b] + bi].push_back(sum[a] + ai);
        }
  }
  printf("%d\n", bipartite());
}
