#include <bits/stdc++.h>
using namespace std;
bool bpm(bool **bpGraph, int u, bool seen[], int matchR[], int N) {
  for (int v = 0; v < N; v++) {
    if (bpGraph[u][v] && !seen[v]) {
      seen[v] = true;
      if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR, N)) {
        matchR[v] = u;
        return true;
      }
    }
  }
  return false;
}
int maxBPM(bool **bpGraph, int M, int N) {
  int matchR[N];
  memset(matchR, -1, sizeof(matchR));
  int result = 0;
  for (int u = 0; u < M; u++) {
    bool seen[N];
    memset(seen, 0, sizeof(seen));
    if (bpm(bpGraph, u, seen, matchR, N)) result++;
  }
  return result;
}
int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  vector<bool> is_prime(1000000 + 1, true);
  vector<int> primes;
  for (int p = 2; p <= 1000000; ++p)
    if (is_prime[p]) {
      primes.push_back(p);
      for (int pp = p; pp <= 1000000; pp += p) is_prime[pp] = false;
    }
  int N, M;
  cin >> N >> M;
  vector<map<int, vector<int> > > factors(N);
  int nodeid1 = 0, nodeid2 = 0;
  for (int i = 0; i < N; ++i) {
    int a;
    cin >> a;
    for (int p : primes) {
      while (a % p == 0) {
        if (i % 2 == 0)
          factors[i][p].push_back(nodeid1++);
        else
          factors[i][p].push_back(nodeid2++);
        a /= p;
      }
      if (a == 1) break;
    }
    if (a != 1) {
      if (i % 2 == 0)
        factors[i][a].push_back(nodeid1++);
      else
        factors[i][a].push_back(nodeid2++);
    }
  }
  bool **graph = new bool *[nodeid1];
  for (int i = 0; i < nodeid1; ++i) {
    graph[i] = new bool[nodeid2];
    for (int j = 0; j < nodeid2; ++j) graph[i][j] = false;
  }
  for (int m = 0; m < M; ++m) {
    int i, j;
    cin >> i >> j;
    --i;
    --j;
    for (auto el : factors[i]) {
      auto it = factors[j].find(el.first);
      if (it != factors[j].end()) {
        for (int n1 : el.second) {
          for (int n2 : it->second) {
            if (i % 2 == 0)
              graph[n1][n2] = true;
            else
              graph[n2][n1] = true;
          }
        }
      }
    }
  }
  cout << maxBPM(graph, nodeid1, nodeid2) << endl;
  return 0;
}
