#include <bits/stdc++.h>
using namespace std;
const long long mod = (long long)1e9 + 7;
const long long inf = 372837928372;
map<long long, long long> factor(long long n) {
  map<long long, long long> v;
  for (long long j = 2; j * j <= n; j++) {
    while (n % j == 0) {
      n /= j;
      v[j]++;
    }
  }
  if (n != 1) v[n]++;
  return v;
}
struct edge {
  int from;
  int to;
  long long flow = 0;
  long long cap;
  edge(int from, int to, long long cap) : from(from), to(to), cap(cap) {}
};
struct dinic {
  vector<int> par, dis;
  int n;
  int s;
  int t;
  queue<int> q;
  vector<vector<int>> g;
  vector<edge> eg;
  dinic(int n, int s, int t) : n(n), s(s), t(t) {
    par.assign(n, -1);
    dis.assign(n, 0);
    g.resize(n);
  }
  void add_edge(int u, int v, long long cap) {
    g[u].emplace_back(eg.size());
    eg.emplace_back(u, v, cap);
    g[v].emplace_back(eg.size());
    eg.emplace_back(v, u, 0);
  }
  bool bfs() {
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (int i = 0; i < (int)g[x].size(); i++) {
        int id = g[x][i];
        if (eg[id].cap - eg[id].flow < 1) continue;
        if (dis[eg[id].to] != -1) continue;
        dis[eg[id].to] = dis[x] + 1;
        q.push(eg[id].to);
      }
    }
    return dis[t] != -1;
  }
  long long dfs(int u, long long f) {
    if (f == 0) return 0;
    if (u == t) return f;
    for (int& id_ = par[u]; id_ < (int)g[u].size(); id_++) {
      int id = g[u][id_];
      if (dis[eg[id].to] != dis[u] + 1 || eg[id].cap - eg[id].flow < 1)
        continue;
      long long f1 = dfs(eg[id].to, min(f, eg[id].cap - eg[id].flow));
      if (f1 == 0) continue;
      eg[id].flow += f1;
      eg[id ^ 1].flow -= f1;
      return f1;
    }
    return 0;
  }
  long long get_max_flow() {
    long long flow = 0;
    while (true) {
      dis.assign(n, -1);
      dis[s] = 0;
      q.push(s);
      if (!bfs()) break;
      par.assign(n, 0);
      while (long long temp = dfs(s, inf)) {
        flow += temp;
      }
    }
    return flow;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.setf(ios::fixed), cout.precision(20);
  long long n, m;
  cin >> n >> m;
  long long arr[n];
  map<long long, map<long long, long long>> v;
  long long cnt = 0;
  for (long long i = 0; i < n; i++) {
    cin >> arr[i];
    if (arr[i] == 1)
      continue;
    else {
      v[i] = factor(arr[i]);
      cnt += v[i].size();
    }
  }
  vector<vector<pair<long long, long long>>> g(cnt + 2);
  vector<long long> cap(cnt + 1);
  long long cc = 1;
  map<pair<long long, long long>, long long> ind;
  for (long long i = 0; i < n; i++) {
    if (!v[i].empty()) {
      for (auto x : v[i]) {
        cap[cc] = x.second;
        ind[make_pair(i, x.first)] = cc;
        cc++;
      }
    }
  }
  vector<vector<long long>> ed(n);
  for (long long i = 0; i < m; i++) {
    long long a;
    long long b;
    cin >> a >> b;
    a--;
    b--;
    if (a & 1) swap(a, b);
    ed[a].push_back(b);
  }
  cc = 1;
  for (long long i = 0; i < n; i++) {
    if (i % 2 == 0 && !v[i].empty()) {
      for (auto x : v[i]) {
        g[0].push_back({cc, x.second});
        for (long long j = 0; j < (long long)ed[i].size(); j++) {
          if (ind.find(make_pair(ed[i][j], x.first)) != ind.end()) {
            g[cc].push_back({ind[make_pair(ed[i][j], x.first)], inf});
          }
        }
        cc++;
      }
    }
    if (i % 2 == 1 && !v[i].empty()) {
      for (auto x : v[i]) {
        g[cc].push_back({cnt + 1, x.second});
        cc++;
      }
    }
  }
  dinic din(cnt + 2, 0, cnt + 1);
  for (long long i = 0; i < (long long)g.size(); i++) {
    for (auto xx : g[i]) {
      din.add_edge(i, xx.first, xx.second);
    }
  }
  cout << din.get_max_flow() << "\n";
  return 0;
}
