#include <bits/stdc++.h>
using namespace std;
int capacity[107][107];
vector<int> adj[107];
set<int> primes;
int n, m;
int a[107];
int bfs(int s, int t, vector<int>& parent) {
  fill(parent.begin(), parent.end(), -1);
  parent[s] = -2;
  queue<pair<int, int>> q;
  q.push({s, 0x3f3f3f3f});
  while (!q.empty()) {
    int v = q.front().first;
    int flow = q.front().second;
    q.pop();
    for (int next : adj[v]) {
      if (parent[next] == -1 and capacity[v][next]) {
        parent[next] = v;
        int newflow = min(flow, capacity[v][next]);
        if (next == t) return newflow;
        q.push({next, newflow});
      }
    }
  }
  return 0;
}
int maxflow(int s, int t) {
  int flow = 0, newflow;
  vector<int> parent(107);
  while (newflow = bfs(s, t, parent)) {
    flow += newflow;
    int cur = t;
    while (cur != s) {
      int p = parent[cur];
      capacity[p][cur] -= newflow;
      capacity[cur][p] += newflow;
      cur = p;
    }
  }
  return flow;
}
void addPrimes(int p) {
  for (int i = 2; i * i <= p; i++) {
    if (p % i == 0) {
      while (p % i == 0) p /= i;
      primes.insert(i);
    }
  }
  if (p > 1) primes.insert(p);
}
int matching(int p) {
  int s = 107 - 1, t = 107 - 2;
  for (int i = 0; i < 107; i++)
    for (int j = 0; j < 107; j++) capacity[i][j] = 0;
  for (int i = 1; i <= n; i += 2)
    for (auto x : adj[i]) capacity[i][x] = 100000;
  for (int i = 1; i <= n; i++) {
    int ct = 0, cpy = a[i];
    while (cpy % p == 0) {
      cpy /= p;
      ct++;
    }
    if (i % 2 == 1)
      capacity[s][i] = ct;
    else
      capacity[i][t] = ct;
  }
  return maxflow(s, t);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) {
    int p, q;
    cin >> p >> q;
    adj[p].push_back(q);
    adj[q].push_back(p);
  }
  int s = 107 - 1, t = 107 - 2;
  for (int i = 1; i <= n; i += 2) {
    adj[s].push_back(i);
    adj[i].push_back(s);
  }
  for (int i = 2; i <= n; i += 2) {
    adj[i].push_back(t);
    adj[t].push_back(i);
  }
  for (int i = 1; i <= n; i++) addPrimes(a[i]);
  int sum = 0;
  for (auto x : primes) sum += matching(x);
  cout << sum << endl;
}
