#include <bits/stdc++.h>
using namespace std;
int a[105], node, par[5005];
vector<pair<int, int> > v[105];
vector<int> adj[5005];
int cap[5005][5005];
int bfs(int s, int t) {
  for (int i = 1; i < 5005; i++) par[i] = -1;
  par[s] = -2;
  queue<pair<int, int> > q;
  q.push({s, 100000000});
  while (!q.empty()) {
    int n = q.front().first;
    int flow = q.front().second;
    q.pop();
    for (int x : adj[n]) {
      if (par[x] == -1 && cap[n][x] > 0) {
        par[x] = n;
        int n_flow = min(flow, cap[n][x]);
        if (x == t) return n_flow;
        q.push({x, n_flow});
      }
    }
  }
  return 0;
}
int flow_cal(int s, int e) {
  int flow = 0;
  while (1) {
    int newflow = bfs(s, e);
    if (!newflow) break;
    flow += newflow;
    int nod = e;
    while (nod != s) {
      cap[par[nod]][nod] -= newflow;
      cap[nod][par[nod]] += newflow;
      nod = par[nod];
    }
  }
  return flow;
}
int main() {
  ++node;
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    for (long long j = 2LL; j * j <= a[i]; j++) {
      while (a[i] % j == 0) {
        v[i].push_back({j, ++node});
        a[i] /= j;
      }
    }
    if (a[i] > 1) {
      v[i].push_back({a[i], ++node});
    }
  }
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    if (x % 2) swap(x, y);
    for (auto ff : v[x]) {
      for (auto ss : v[y]) {
        if (ff.first == ss.first) {
          cap[ff.second][ss.second] = 1;
          adj[ff.second].push_back(ss.second);
          adj[ss.second].push_back(ff.second);
        }
      }
    }
  }
  ++node;
  for (int i = 2; i <= n; i += 2) {
    for (auto xx : v[i]) {
      cap[1][xx.second] = 1;
      adj[1].push_back(xx.second);
      adj[xx.second].push_back(1);
    }
  }
  for (int i = 1; i <= n; i += 2) {
    for (auto xx : v[i]) {
      cap[xx.second][node] = 1;
      adj[node].push_back(xx.second);
      adj[xx.second].push_back(node);
    }
  }
  cout << flow_cal(1, node) << endl;
}
