#include <bits/stdc++.h>
using namespace std;
const int inf = 5000;
const int MAXN = 200, MAXE = 2 * MAXN;
int src, snk, nNode, nEdge;
int Q[MAXN], fin[MAXN], pro[MAXN], dist[MAXN];
int flow[MAXE], cap[MAXE], Next[MAXE], to[MAXE];
inline void init(int _src, int _snk, int _n) {
  src = _src, snk = _snk, nNode = _n, nEdge = 0;
  memset(fin, -1, sizeof(fin));
}
inline void add(int u, int v, int c) {
  to[nEdge] = v, cap[nEdge] = c, flow[nEdge] = 0, Next[nEdge] = fin[u],
  fin[u] = nEdge++;
  to[nEdge] = u, cap[nEdge] = 0, flow[nEdge] = 0, Next[nEdge] = fin[v],
  fin[v] = nEdge++;
}
bool bfs() {
  int st, en;
  memset(dist, -1, sizeof(dist));
  dist[src] = st = en = 0;
  Q[en++] = src;
  while (st < en) {
    int u = Q[st++];
    for (int i = fin[u]; i >= 0; i = Next[i]) {
      int v = to[i];
      if (flow[i] < cap[i] && dist[v] == -1) {
        dist[v] = dist[u] + 1;
        Q[en++] = v;
      }
    }
  }
  return (dist[snk] != -1);
}
int dfs(int u, int fl) {
  if (u == snk) return fl;
  for (int &e = pro[u]; e >= 0; e = Next[e]) {
    int v = to[e];
    if (flow[e] < cap[e] && dist[v] == dist[u] + 1) {
      int df = dfs(v, min(cap[e] - flow[e], fl));
      if (df > 0) {
        flow[e] += df;
        flow[e ^ 1] -= df;
        return df;
      }
    }
  }
  return 0;
}
long long dinitz() {
  long long ret = 0;
  while (bfs()) {
    for (int i = 0; i <= nNode; i++) pro[i] = fin[i];
    while (true) {
      int df = dfs(src, inf);
      if (df)
        ret += (long long)df;
      else
        break;
    }
  }
  return ret;
}
int arr[MAXN], x[MAXN], y[MAXN];
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &x[i], &y[i]);
    if (x[i] % 2 == 0) swap(x[i], y[i]);
  }
  set<int> prime;
  for (int i = 1; i <= n; i++) {
    int nw = arr[i];
    for (int p = 2; p * p <= nw; p++) {
      int cnt = 0;
      while (nw % p == 0) {
        ++cnt, nw /= p;
      }
      if (cnt) prime.insert(p);
    }
    if (nw > 1) prime.insert(nw);
  }
  long long tot = 0;
  for (set<int>::iterator it = prime.begin(); it != prime.end(); it++) {
    int p = *it;
    int s = 0, t = n + 1;
    init(s, t, n + 2);
    for (int i = 1; i <= n; i++) {
      int nw = arr[i], cnt = 0;
      while (nw % p == 0) ++cnt, nw /= p;
      if (cnt) {
        if (i % 2 == 1)
          add(s, i, cnt);
        else
          add(i, t, cnt);
      }
    }
    for (int i = 1; i <= m; i++) {
      add(x[i], y[i], inf);
    }
    tot += dinitz();
  }
  printf("%lld\n", tot);
  return 0;
}
