#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxv = 105;
const int inf = 0x3f3f3f3f;
int prime[maxn];
bool is_prime[maxn + 1];
int sieve(int n) {
  int p = 0;
  for (int i = 0; i <= n; i++) is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; i++)
    if (is_prime[i]) {
      prime[p++] = i;
      for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
    }
  return p;
}
struct edge {
  int to, cap, rev;
  edge() {}
  edge(int t, int c, int r) : to(t), cap(c), rev(r) {}
};
vector<edge> G[maxv];
int level[maxv];
int iter[maxv];
void addedge(int from, int to, int cap) {
  G[from].push_back(edge(to, cap, G[to].size()));
  G[to].push_back(edge(from, 0, G[from].size() - 1));
}
void bfs(int s) {
  memset(level, -1, sizeof level);
  queue<int> que;
  level[s] = 0;
  que.push(s);
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    for (unsigned int i = 0; i < G[v].size(); i++) {
      edge &e = G[v][i];
      if (e.cap > 0 && level[e.to] < 0) {
        level[e.to] = level[v] + 1;
        que.push(e.to);
      }
    }
  }
}
int dfs(int v, int t, int f) {
  if (v == t) return f;
  for (int &i = iter[v]; i < (int)G[v].size(); i++) {
    edge &e = G[v][i];
    if (e.cap > 0 && level[v] < level[e.to]) {
      int d = dfs(e.to, t, min(f, e.cap));
      if (d > 0) {
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}
int max_flow(int s, int t) {
  int flow = 0;
  for (;;) {
    bfs(s);
    if (level[t] < 0) return flow;
    memset(iter, 0, sizeof iter);
    int f;
    while ((f = dfs(s, t, inf)) > 0) flow += f;
  }
}
int n, m, prinum, s, t;
int a[maxv], b[maxv][2];
void init(int num) {
  for (int i = 0; i < num; i++) G[i].clear();
}
void solve() {
  int res = 0;
  for (int i = 0; i < prinum; i++) {
    init(t + 1);
    for (int j = 0; j < m; j++) {
      if (a[b[j][0]] % prime[i] == 0 && a[b[j][1]] % prime[i] == 0) {
        if (b[j][0] & 1)
          addedge(b[j][0], b[j][1], inf);
        else
          addedge(b[j][1], b[j][0], inf);
      }
    }
    for (int j = 0; j < n; j++) {
      int cnt = 0;
      while (a[j] % prime[i] == 0) {
        cnt++;
        a[j] /= prime[i];
      }
      if (cnt) {
        if (j & 1)
          addedge(s, j, cnt);
        else
          addedge(j, t, cnt);
      }
    }
    res += max_flow(s, t);
  }
  init(t + 1);
  for (int i = 0; i < n; i++)
    if ((i & 1) && a[i] != 1)
      addedge(s, i, 1);
    else if (!(i & 1) && a[i] != 1)
      addedge(i, t, 1);
  for (int i = 0; i < m; i++)
    if (a[b[i][0]] == a[b[i][1]] && a[b[i][0]] != 1) {
      if (b[i][0] & 1)
        addedge(b[i][0], b[i][1], inf);
      else
        addedge(b[i][1], b[i][0], inf);
    }
  res += max_flow(s, t);
  printf("%d\n", res);
}
int main() {
  prinum = sieve(maxn);
  while (scanf("%d%d", &n, &m) == 2) {
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) {
      scanf("%d%d", &b[i][0], &b[i][1]);
      b[i][0]--;
      b[i][1]--;
    }
    s = n, t = s + 1;
    solve();
  }
  return 0;
}
