#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long int MOD = 1e9 + 7;
long long int n, m, k, res = 0, ans = 0, sm = 0, edge = -1;
long long int a[500050], b[500050], group[500005] = {0}, node1[50005],
                                    node2[50005], vis[500005] = {0};
set<long long int> st, st1, st2;
set<long long int> stres;
string s, s1, s2, s3, s4;
vector<long long int> v, vnode, vans, v1, v2;
vector<pair<int, int> > vv, vv1, adj[500005];
vector<pair<int, pair<int, int> > > vvv;
priority_queue<long long int> q;
map<pair<int, int>, long long int> mp;
set<long long int>::iterator it, it1, it2;
int voyel(char c) {
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'y')
    return 1;
  return 0;
}
class BipGraph {
  int m, n;
  vector<int> *adj;
  int *pairU, *pairV, *dist;

 public:
  BipGraph(int m, int n);
  void addEdge(int u, int v);
  bool bfs();
  bool dfs(int u);
  int hopcroftKarp();
};
int BipGraph::hopcroftKarp() {
  pairU = new int[m + 1];
  pairV = new int[n + 1];
  dist = new int[m + 1];
  for (int u = 0; u < m; u++) pairU[u] = 0;
  for (int v = 0; v < n; v++) pairV[v] = 0;
  int result = 0;
  while (bfs()) {
    for (int u = 1; u <= m; u++)
      if (pairU[u] == 0 && dfs(u)) result++;
  }
  return result;
}
bool BipGraph::bfs() {
  queue<int> Q;
  for (int u = 1; u <= m; u++) {
    if (pairU[u] == 0) {
      dist[u] = 0;
      Q.push(u);
    } else
      dist[u] = INT_MAX;
  }
  dist[0] = INT_MAX;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    if (dist[u] < dist[0]) {
      vector<int>::iterator it;
      for (it = adj[u].begin(); it != adj[u].end(); ++it) {
        int v = *it;
        if (dist[pairV[v]] == INT_MAX) {
          dist[pairV[v]] = dist[u] + 1;
          Q.push(pairV[v]);
        }
      }
    }
  }
  return (dist[0] != INT_MAX);
}
bool BipGraph::dfs(int u) {
  if (u != 0) {
    vector<int>::iterator it;
    for (it = adj[u].begin(); it != adj[u].end(); ++it) {
      int v = *it;
      if (dist[pairV[v]] == dist[u] + 1) {
        if (dfs(pairV[v]) == true) {
          pairV[v] = u;
          pairU[u] = v;
          return true;
        }
      }
    }
    dist[u] = INT_MAX;
    return false;
  }
  return true;
}
BipGraph::BipGraph(int m, int n) {
  this->m = m;
  this->n = n;
  adj = new vector<int>[m + 1];
}
void BipGraph::addEdge(int u, int v) { adj[u].push_back(v); }
vector<long long int> factorize(long long int x) {
  long long int temp = x;
  vector<long long int> ans;
  while (temp % 2 == 0) {
    ans.push_back(2);
    temp >>= 1;
  }
  int j;
  for (j = 3; j * j <= temp; j += 2) {
    while (temp % j == 0) {
      ans.push_back(j);
      temp /= j;
    }
  }
  if (temp > 2) ans.push_back(temp);
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long int i = 0, j = 0, x, y, z = 0, mx = 0, nb0 = 0, nb = 0, nbmax = 0,
                nbinf = 0, mm = 5e9, idx = 0, ok = 0, l, r, negatif = 0,
                positif = 0, q, w, d;
  char c;
  cin >> n >> m;
  for (i = 1; i <= n; i++) cin >> a[i];
  long long int nbnode = 0;
  BipGraph g(50000, 50000);
  long long int idx1 = 0, idx2 = 0;
  while (m--) {
    cin >> x >> y;
    if (!(x & 1)) swap(x, y);
    mp[{x, y}] = 1;
    mp[{y, x}] = 1;
    v = factorize(a[x]);
    if (!vis[x])
      for (i = 0; i < ((long long int)((v).size())); i++) {
        nbnode++;
        v1.push_back(v[i]);
        group[nbnode] = x;
        node1[idx1] = nbnode;
        idx1++;
        vis[x] = 1;
      }
    v.clear();
    v = factorize(a[y]);
    if (!vis[y])
      for (i = 0; i < ((long long int)((v).size())); i++) {
        nbnode++;
        v2.push_back(v[i]);
        group[nbnode] = y;
        node2[idx2] = nbnode;
        idx2++;
        vis[y] = 1;
      }
  }
  for (i = 0; i < ((long long int)((v1).size())); i++) {
    for (j = 0; j < ((long long int)((v2).size())); j++) {
      long long int nod1 = node1[i];
      long long int nod2 = node2[j];
      if (mp[{group[nod1], group[nod2]}] && v1[i] == v2[j])
        g.addEdge(nod1, nod2);
    }
  }
  res = g.hopcroftKarp();
  cout << res;
  return 0;
}
