#include <bits/stdc++.h>
using namespace std;
struct edge {
  int from, to, cap, flow;
};
vector<int> pr, g[100005];
vector<edge> e;
bool has[100005];
int ptr[100005], dist[100005], T, cnt;
map<int, int> idx;
map<int, int>::iterator it;
void add_edge(int from, int to, int cap) {
  edge e1 = {from, to, cap, 0};
  edge e2 = {to, from, 0, 0};
  g[from].push_back((int)e.size());
  e.push_back(e1);
  g[to].push_back((int)e.size());
  e.push_back(e2);
}
void sieve() {
  int i, j;
  for (i = 2; i * i < 100005; i++) {
    if (!has[i]) {
      pr.push_back(i);
      for (j = i * i; j < 100005; j += i) has[j] = 1;
    }
  }
  for (; i < 100005; i++)
    if (!has[i]) pr.push_back(i);
}
bool bfs() {
  queue<int> q;
  int id, cur, v, i;
  memset(dist, 0, sizeof(dist));
  q.push(0);
  dist[0] = 1;
  while (!q.empty()) {
    cur = q.front();
    q.pop();
    for (i = 0; i < g[cur].size(); i++) {
      id = g[cur][i];
      v = e[id].to;
      if (!dist[v] && e[id].flow < e[id].cap) {
        dist[v] = dist[cur] + 1;
        q.push(v);
      }
    }
  }
  return dist[T] > 1;
}
int dfs(int u, int mf) {
  if (!mf) return 0;
  if (u == T) return mf;
  int id, v, val;
  for (; ptr[u] < g[u].size(); ++ptr[u]) {
    id = g[u][ptr[u]], v = e[id].to;
    if (dist[v] != dist[u] + 1) continue;
    val = dfs(v, min(mf, e[id].cap - e[id].flow));
    if (val) {
      e[id].flow += val;
      e[id ^ 1].flow -= val;
      return val;
    }
  }
  return 0;
}
int main() {
  sieve();
  int n, m, x, y, ans = 0, id, t1;
  scanf("%d", &n);
  scanf("%d", &m);
  T = 100000;
  cnt = 1;
  for (int l = int(1); l <= int(n); l++) {
    scanf("%d", &x);
    for (vector<int>::iterator it = (pr).begin(); it != (pr).end(); it++) {
      if (x % *it == 0) {
        if (idx.find(*it) != idx.end())
          id = idx[*it];
        else
          id = cnt, idx[*it] = cnt++;
        t1 = 0;
        while (x % *it == 0) {
          t1++;
          x /= *it;
        }
        assert(t1 < 2000000000);
        if (l % 2)
          add_edge(0, l * 500 + id, t1);
        else
          add_edge(l * 500 + id, T, t1);
      }
    }
    if (x != 1) {
      if (idx.find(x) != idx.end())
        id = idx[x];
      else
        id = cnt, idx[x] = cnt++;
      if (l % 2)
        add_edge(0, l * 500 + id, 1);
      else
        add_edge(l * 500 + id, T, 1);
    }
  }
  for (int l = int(1); l <= int(m); l++) {
    scanf("%d", &x);
    scanf("%d", &y);
    if (y % 2) swap(x, y);
    for (int i = int(1); i <= int(500); i++)
      add_edge(x * 500 + i, y * 500 + i, 2000000000);
  }
  ans = 0, x = 10;
  while (bfs() && x--) {
    memset(ptr, 0, sizeof(ptr));
    while (t1 = dfs(0, 2000000000)) {
      ans += t1;
    }
  }
  cout << ans << endl;
  return 0;
}
