#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const int MAXN = 5e3 + 3;
const long long INF = 1LL << 61;
long long a[MAXN], caps[MAXN];
map<pair<int, int>, long long> mapa;
struct edge {
  int a, b;
  long long cap, flow;
};
int N, M, s, t, d[MAXN], ptr[MAXN];
vector<edge> e;
vector<int> G[MAXN];
void add_edge(int a, int b, long long cap) {
  edge e1 = {a, b, cap, 0};
  edge e2 = {b, a, 0, 0};
  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, (N + 1) * sizeof d[0]);
  d[s] = 0;
  while (!q.empty() && d[t] == -1) {
    int v = q.front();
    q.pop();
    for (int i = (int)0; i < (int)G[v].size(); i++) {
      int id = G[v][i], to = e[id].b;
      if (d[to] == -1 && e[id].flow < e[id].cap) {
        q.push(to);
        d[to] = d[v] + 1;
      }
    }
  }
  return d[t] != -1;
}
long long dfs(int v, long long flow) {
  if (!flow) return 0;
  if (v == t) return flow;
  for (; ptr[v] < (int)G[v].size(); ++ptr[v]) {
    int id = G[v][ptr[v]], to = e[id].b;
    if (d[to] != d[v] + 1) continue;
    int pushed = dfs(to, min(flow, (long long)e[id].cap - e[id].flow));
    if (pushed) {
      e[id].flow += pushed;
      e[id ^ 1].flow -= pushed;
      return pushed;
    }
  }
  return 0;
}
long long dinic() {
  long long flow = 0;
  while (true) {
    if (!bfs()) break;
    memset(ptr, 0, (N + 1) * sizeof ptr[0]);
    while (long long pushed = dfs(s, INF)) flow += pushed;
  }
  return flow;
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = (int)0; i < (int)n; i++) scanf("%lld", &a[i]);
  N = n;
  long long inf = 1e9, k2 = 0;
  for (int j = (int)0; j < (int)n; j++) {
    if (j % 2) continue;
    long long ans = a[j];
    int num = sqrt(ans) + 1;
    long long cap = 0;
    for (int i = (int)2; i < (int)num; i++) {
      long long f = 0;
      while (ans % i == 0) {
        ans /= 2;
        f++;
        cap++;
      }
      if (f) {
        mapa[{i, j}] = N + k2;
        add_edge(N + k2, j, f);
        k2++;
      }
    }
    if (ans != 1) {
      cap++;
      mapa[{ans, j}] = N + k2;
      add_edge(N + k2, j, 1);
      k2++;
    }
    caps[j] = cap;
  }
  for (int i = (int)0; i < (int)m; i++) {
    int d, c;
    scanf("%d %d", &d, &c);
    d--;
    c--;
    if (!(d % 2)) swap(d, c);
    int j = d;
    long long ans = a[j];
    int num = sqrt(ans) + 1;
    long long cap = 0;
    for (int i = (int)2; i < (int)num; i++) {
      long long f = 0;
      while (ans % i == 0) {
        ans /= 2;
        f++;
        cap++;
      }
      if (mapa.count({i, c}) && f) {
        if (!mapa.count({i, d})) {
          mapa[{i, d}] = N + k2;
          add_edge(d, N + k2, f);
          k2++;
        }
        add_edge(mapa[{i, d}], mapa[{i, c}], f);
      }
    }
    if (ans != 1) {
      cap++;
      if (mapa.count({ans, c})) {
        if (!mapa.count({ans, d})) {
          mapa[{ans, d}] = N + k2;
          add_edge(d, N + k2, 1);
          k2++;
        }
        add_edge(mapa[{ans, d}], mapa[{ans, c}], 1);
      }
    }
    caps[j] = cap;
  }
  s = N + k2;
  t = N + k2 + 1;
  for (int i = (int)0; i < (int)n; i++) {
    if (i % 2)
      add_edge(s, i, caps[i]);
    else
      add_edge(i, t, caps[i]);
  }
  N += (k2 + 2);
  long long flow = dinic();
  printf("%lld", flow);
}
