#include <bits/stdc++.h>
using namespace std;
const int MAXP = 31625;
const int MAXN = 102;
struct Edge {
  int ind, cap;
};
int N, M, arr[MAXN], from[MAXN], to[MAXN], primeFactors[102][3605],
    capacity[MAXN * 2][MAXN * 2];
map<int, int> inPrimes;
bool isPrime[MAXP], vis[MAXN * 2];
vector<int> primes;
void getPrimeFactors(int x, int ind) {
  for (int i = 0; i < (int)primes.size(); i++) {
    while (x % primes[i] == 0) {
      primeFactors[ind][i]++;
      x /= primes[i];
    }
  }
  if (x > 1) {
    if (!inPrimes.count(x)) {
      inPrimes[x] = primes.size();
      primes.push_back(x);
    }
    primeFactors[ind][inPrimes[x]]++;
  }
}
int maxFlow(int ind, int mx, int dst) {
  if (mx <= 0) return 0;
  if (ind == dst) return mx;
  vis[ind] = true;
  for (int i = 0; i <= N * 2 + 1; i++) {
    if (!capacity[ind][i] || vis[i]) continue;
    int m = maxFlow(i, min(mx, capacity[ind][i]), dst);
    if (m > 0) {
      capacity[ind][i] -= m;
      capacity[i][ind] += m;
      vis[ind] = false;
      return m;
    }
  }
  vis[ind] = false;
  return 0;
}
int main() {
  for (int i = 0; i < MAXP; i++) isPrime[i] = 1;
  for (int i = 2; i <= MAXP; i++)
    if (isPrime[i]) {
      primes.push_back(i);
      for (int j = i * i; j <= MAXP; j += i) isPrime[j] = false;
    }
  scanf("%d %d", &N, &M);
  for (int i = 0; i < N; i++) {
    scanf("%d", &arr[i]);
    getPrimeFactors(arr[i], i + 1);
  }
  for (int i = 0; i < M; i++) scanf("%d %d", &from[i], &to[i]);
  int ret = 0;
  for (int i = 0; i < (int)primes.size(); i++) {
    memset(capacity, 0, sizeof capacity);
    for (int j = 1; j <= N; j++) {
      capacity[0][j] = primeFactors[j][i];
      capacity[j + N][N * 2 + 1] = primeFactors[j][i];
    }
    for (int j = 0; j < M; j++)
      capacity[from[j]][to[j] + N] = capacity[to[j]][from[j] + N] = 1 << 30;
    int m = true;
    while (m) {
      m = maxFlow(0, 1 << 30, N * 2 + 1);
      ret += m;
    }
  }
  printf("%d\n", ret / 2);
}
