#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
int n, m, a, b;
vector<int> N;
int cap[102][102], flow[102][102];
bool connection[100][100];
set<int> prime;
int source = 100, sink = 101;
int maxFlow(int p) {
  memset(flow, 0, sizeof(flow));
  memset(cap, 0, sizeof(cap));
  for (int i = 0; i < (int)n; i++) {
    int cnt = 0;
    while (N[i] % p == 0) {
      cnt++;
      N[i] /= p;
    }
    if (i % 2 == 0) {
      cap[source][i] = cnt;
      for (int j = 0; j < (int)n; j++) {
        if (connection[i][j]) cap[i][j] = cnt;
      }
    } else {
      cap[i][sink] = cnt;
    }
  }
  int totalFlow = 0;
  while (1) {
    vector<int> parent(102, -1);
    queue<int> q;
    parent[source] = source;
    q.push(source);
    while (!q.empty() && parent[sink] == -1) {
      int here = q.front();
      q.pop();
      for (int there = 0; there < (int)102; there++) {
        if (cap[here][there] - flow[here][there] > 0 && parent[there] == -1) {
          q.push(there);
          parent[there] = here;
        }
      }
    }
    if (parent[sink] == -1) break;
    int amount = INT_MAX;
    for (int p = sink; p != parent[p]; p = parent[p]) {
      amount = min(amount, cap[parent[p]][p] - flow[parent[p]][p]);
    }
    for (int p = sink; p != parent[p]; p = parent[p]) {
      flow[parent[p]][p] += amount;
      flow[p][parent[p]] -= amount;
    }
    totalFlow += amount;
  }
  return totalFlow;
}
void addPrime(int a) {
  for (int i = 2; i * i <= a; i++) {
    if (a % i == 0) prime.insert(i);
    while (a % i == 0) a /= i;
  }
  if (a > 1) prime.insert(a);
}
int main() {
  memset(connection, 0, sizeof(connection));
  cin >> n >> m;
  for (int i = 0; i < (int)n; i++) {
    cin >> a;
    N.push_back(a);
    addPrime(a);
  }
  for (int i = 0; i < (int)m; i++) {
    cin >> a >> b;
    if (a % 2 == 0) swap(a, b);
    connection[a - 1][b - 1] = 1;
  }
  int ret = 0;
  for (set<int>::iterator it = prime.begin(); it != prime.end(); it++) {
    ret += maxFlow(*it);
  }
  cout << ret << endl;
}
