#include <bits/stdc++.h>
const int MAX = 1e2 + 5;
const int MAXN = 1e5 + 5;
const int maxn = 205;
const int INF = 1e9 + 5;
const long long INF2 = 4e18 + 5;
const double M = 4e18;
using namespace std;
const int MOD = 1e9 + 7;
const double eps = 0.000000001;
struct Edge {
  int from, to, cap, flow;
  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
struct EdmondsKarp {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  int a[maxn];
  int p[maxn];
  void init(int n) {
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }
  int Maxflow(int s, int t) {
    int flow = 0;
    for (;;) {
      memset(a, 0, sizeof(a));
      queue<int> que;
      que.push(s);
      a[s] = INF;
      while (!que.empty()) {
        int x = que.front();
        que.pop();
        for (int i = 0; i < G[x].size(); i++) {
          Edge &e = edges[G[x][i]];
          if (!a[e.to] && e.cap > e.flow) {
            p[e.to] = G[x][i];
            a[e.to] = min(a[x], e.cap - e.flow);
            que.push(e.to);
          }
        }
        if (a[t]) break;
      }
      if (!a[t]) break;
      for (int u = t; u != s; u = edges[p[u]].from) {
        edges[p[u]].flow += a[t];
        edges[p[u] ^ 1].flow -= a[t];
      }
      flow += a[t];
    }
    return flow;
  }
};
EdmondsKarp notle;
bool prime[MAXN];
void getprime() {
  int da = 1e5;
  memset(prime, true, sizeof(prime));
  prime[1] = false;
  for (int i = 2; i <= da; i++) {
    if (prime[i]) {
      for (int j = 2; i * j <= da; j++) prime[i * j] = false;
    }
  }
}
int getnum(int &x, int p) {
  int re = 0;
  while (x % p == 0) {
    x /= p;
    ++re;
  }
  return re;
}
int n, m;
int a[MAX];
int x[MAX], y[MAX], an;
int solve(int p) {
  int num[MAX];
  memset(num, 0, sizeof(num));
  notle.init(n + 2);
  num[0] = num[n + 1] = INF;
  for (int i = 1; i <= n; i++) num[i] = getnum(a[i], p);
  for (int i = 1; i <= n; i += 2) notle.AddEdge(0, i, num[i]);
  for (int i = 2; i <= n; i += 2) notle.AddEdge(i, n + 1, num[i]);
  for (int i = 1; i <= m; i++) {
    if (x[i] % 2 == 1)
      notle.AddEdge(x[i], y[i], min(num[x[i]], num[y[i]]));
    else
      notle.AddEdge(y[i], x[i], min(num[x[i]], num[y[i]]));
  }
  return notle.Maxflow(0, n + 1);
}
int main() {
  scanf("%d%d", &n, &m);
  getprime();
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &x[i], &y[i]);
  }
  for (int i = 2; i <= 1e5; i++) {
    if (prime[i]) an += solve(i);
  }
  notle.init(n + 2);
  for (int i = 1; i <= n; i += 2) notle.AddEdge(0, i, a[i] != 1 ? 1 : 0);
  for (int i = 2; i <= n; i += 2) notle.AddEdge(i, n + 1, a[i] != 1 ? 1 : 0);
  for (int i = 1; i <= m; i++) {
    if (x[i] % 2 == 1)
      notle.AddEdge(x[i], y[i], (a[x[i]] != 1 && a[x[i]] == a[y[i]]) ? 1 : 0);
    else
      notle.AddEdge(y[i], x[i], (a[x[i]] != 1 && a[x[i]] == a[y[i]]) ? 1 : 0);
  }
  an += notle.Maxflow(0, n + 1);
  printf("%d\n", an);
}
