#include <bits/stdc++.h>
using namespace std;
using namespace std;
const int MAXN = 5000 + 5;
const int INF = 30000;
const int eps = 0;
struct edge {
  int a, b;
  int cap, flow;
  int yo, x, y;
};
struct Dinic {
  int s, t, d[MAXN], ptr[MAXN];
  vector<edge> e;
  vector<int> g[MAXN];
  void init() {
    e.clear();
    memset(d, 0, sizeof(d));
    for (int i = 0; i < MAXN; i++) g[i].clear();
  }
  void addEdge(int a, int b, int cap, int x = -1, int y = -1) {
    edge e1 = {a, b, cap, 0, 1, x, y};
    edge e2 = {b, a, 0, 0, 0, x, y};
    g[a].push_back((int)e.size());
    e.push_back(e1);
    g[b].push_back((int)e.size());
    e.push_back(e2);
  }
  bool bfs() {
    queue<int> Q;
    Q.push(s);
    memset(d, -1, sizeof(d));
    d[s] = 0;
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (int i = 0; i < g[u].size(); i++) {
        int id = g[u][i];
        int v = e[id].b;
        if (d[v] == -1 && e[id].flow < e[id].cap) {
          Q.push(v);
          d[v] = d[u] + 1;
        }
      }
    }
    return d[t] != -1;
  }
  int dfs(int u, int flow) {
    if (flow <= eps) return 0;
    if (u == t) return flow;
    for (int& i = ptr[u]; i < g[u].size(); i++) {
      int id = g[u][i];
      int v = e[id].b;
      if (d[v] != d[u] + 1) continue;
      int pushed = dfs(v, min(flow, e[id].cap - e[id].flow));
      if (pushed > eps) {
        e[id].flow += pushed;
        e[id ^ 1].flow -= pushed;
        return pushed;
      }
    }
    return 0;
  }
  int dinic() {
    int flow = 0;
    while (true) {
      if (!bfs()) break;
      memset(ptr, 0, sizeof(ptr));
      while (true) {
        int pushed = dfs(s, INF);
        if (pushed <= eps) break;
        flow += pushed;
      }
    }
    return flow;
  }
};
Dinic dinic;
int n, m;
int a[107];
vector<pair<pair<int, int>, int> > prime[107];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  dinic.s = 0;
  dinic.t = 1;
  int offset = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j * j <= a[i]; j++) {
      if (a[i] % j) continue;
      offset++;
      int cnt = 0;
      while (a[i] && a[i] % j == 0) cnt++, a[i] /= j;
      prime[i].push_back({{j, cnt}, offset});
    }
    if (a[i] > 1) {
      offset++;
      prime[i].push_back({{a[i], 1}, offset});
    }
  }
  dinic.t += offset;
  for (int i = 1; i <= n; i++) {
    for (auto e : prime[i]) {
      if (i % 2)
        dinic.addEdge(dinic.s, e.second, e.first.second);
      else
        dinic.addEdge(e.second, dinic.t, e.first.second);
    }
  }
  offset = 0;
  for (int ii = 1; ii <= m; ii++) {
    int i, j;
    scanf("%d %d", &i, &j);
    if (j % 2) swap(i, j);
    auto e1 = prime[i].begin();
    auto e2 = prime[j].begin();
    while (e1 != prime[i].end() && e2 != prime[j].end()) {
      while (e1 != prime[i].end() && e1->first.first < e2->first.first) e1++;
      if (e1 == prime[i].end()) break;
      while (e2 != prime[j].end() && e1->first.first > e2->first.first) e2++;
      if (e2 == prime[j].end()) break;
      if (e1->first.first == e2->first.first) {
        dinic.addEdge(e1->second, e2->second,
                      min(e1->first.second, e2->first.second));
        e1++;
        e2++;
      }
    }
  }
  int ans = dinic.dinic();
  cout << ans << endl;
  return 0;
}
