#include <bits/stdc++.h>
using namespace std;
void solve();
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}
int64_t n, m, nbNodes;
vector<vector<int64_t>> adj;
vector<vector<int64_t>> cap;
int64_t bfs(int64_t s, int64_t t, vector<int64_t> &parent) {
  fill(parent.begin(), parent.end(), -1);
  parent[s] = -2;
  queue<pair<int64_t, int64_t>> q;
  q.push({s, INT_MAX});
  while (!q.empty()) {
    int64_t cur = q.front().first;
    int64_t flow = q.front().second;
    q.pop();
    for (int64_t next : adj[cur]) {
      if (parent[next] == -1 && cap[cur][next]) {
        int64_t newFlow = (flow < cap[cur][next] ? flow : cap[cur][next]);
        parent[next] = cur;
        if (next == t) return newFlow;
        q.push({next, newFlow});
      }
    }
  }
  return 0;
}
int64_t maxFlow(int64_t s, int64_t t) {
  int64_t flow = 0;
  vector<int64_t> parent(nbNodes);
  int64_t newFlow;
  while (newFlow = bfs(s, t, parent)) {
    flow += newFlow;
    int64_t cur = t;
    while (cur != s) {
      int64_t prev = parent[cur];
      cap[prev][cur] -= newFlow;
      cap[cur][prev] += newFlow;
      cur = prev;
    }
  }
  return flow;
}
void solve() {
  cin >> n >> m;
  vector<vector<pair<int64_t, int64_t>>> a(n);
  vector<int64_t> indiceNoeud(n);
  nbNodes = 1;
  for (int64_t i = 0; i < n; i++) {
    int64_t input;
    cin >> input;
    indiceNoeud[i] = nbNodes;
    for (int64_t num = 2; num * num <= input; num++) {
      if (input % num == 0) {
        int64_t count = 0;
        while (input % num == 0) {
          input /= num;
          count++;
        }
        a[i].push_back(make_pair(num, count));
        nbNodes++;
      }
    }
    if (input > 1) {
      a[i].push_back(make_pair(input, 1));
      nbNodes++;
    }
  }
  nbNodes++;
  adj = vector<vector<int64_t>>(nbNodes);
  cap = vector<vector<int64_t>>(nbNodes, vector<int64_t>(nbNodes));
  for (int64_t i_ = 0; i_ < m; i_++) {
    int64_t u, v;
    cin >> u >> v;
    u--;
    v--;
    if (u % 2) swap(u, v);
    for (int64_t i = 0; i < (int64_t)(a[u].size()); i++)
      for (int64_t j = 0; j < (int64_t)(a[v].size()); j++) {
        if (a[u][i].first == a[v][j].first) {
          int64_t n1 = indiceNoeud[u] + i;
          int64_t n2 = indiceNoeud[v] + j;
          adj[n1].push_back(n2);
          adj[n2].push_back(n1);
          cap[n1][n2] = a[u][i].second;
          break;
        }
      }
  }
  for (int64_t u = 1; u < n; u += 2)
    for (int64_t i = 0; i < (int64_t)(a[u].size()); i++) {
      int64_t cur = indiceNoeud[u] + i;
      adj[cur].push_back(nbNodes - 1);
      adj[nbNodes - 1].push_back(cur);
      cap[cur][nbNodes - 1] = a[u][i].second;
    }
  for (int64_t u = 0; u < n; u += 2)
    for (int64_t i = 0; i < (int64_t)(a[u].size()); i++) {
      int64_t cur = indiceNoeud[u] + i;
      adj[cur].push_back(0);
      adj[0].push_back(cur);
      cap[0][cur] = a[u][i].second;
    }
  cout << maxFlow(0, nbNodes - 1);
  return;
}
