#include <bits/stdc++.h>
using namespace std;
long long max(long long a, long long b) {
  if (a > b) {
    return a;
  } else {
    return b;
  }
}
long long min(long long a, long long b) {
  if (a < b) {
    return a;
  } else {
    return b;
  }
}
struct P {
  double x, y;
  P() {}
  P(double x, double y) : x(x), y(y) {}
  P operator+(const P &a) const { return P(x + a.x, y + a.y); }
  P operator-(const P &a) const { return P(x - a.x, y - a.y); }
  double operator^(const P &a) const { return x * a.x + y * a.y; }
  void in() { scanf("%lf%lf", &x, &y); }
  void out() { printf("REQUIRED %.7f %.7f\n", x, y); }
  double dist(P a, P b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  }
  double sqdist(P a, P b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  }
};
int n, m;
int a[300001], b[300001];
int nxt[1000001], dir[1000001], cost[1000001], rev[1000001];
int h;
int visit[300001], c[300001];
int edge[300001];
int l[300001], r[300001];
int lb[300001], ty[1000001];
void insert(int u, int v) {
  nxt[++h] = nxt[u];
  nxt[u] = h;
  dir[h] = v;
  nxt[++h] = nxt[v];
  nxt[v] = h;
  dir[h] = u;
}
void insert2(int u, int v, int id) {
  nxt[++h] = nxt[u];
  nxt[u] = h;
  dir[h] = v;
  rev[h] = h + 1;
  ty[h] = id;
  edge[id] = h;
  nxt[++h] = nxt[v];
  nxt[v] = h;
  dir[h] = u;
  rev[h] = h - 1;
  ty[h] = -1;
}
void DFS2(int p, int color) {
  c[p] = color;
  visit[p] = 1;
  for (int i = nxt[p]; i > 0; i = nxt[i])
    if (visit[dir[i]] == 0) {
      DFS2(dir[i], 1 - color);
    }
}
int s, t;
int lvl[300001];
int q[300001];
bool BFS() {
  for (int i = (1); i <= (2 * n); i++) lvl[i] = -1;
  lvl[s] = 0;
  int top = 0, tail = 0;
  q[top++] = s;
  while (top > tail) {
    int u = q[tail++];
    for (int po = nxt[u]; po > 0; po = nxt[po]) {
      if (lvl[dir[po]] == -1 && cost[po] > 0) {
        lvl[dir[po]] = lvl[u] + 1;
        q[top++] = dir[po];
      }
    }
  }
  return (lvl[t] != -1);
}
int DFS(int u, int flow) {
  if (u == t) return flow;
  int w = flow;
  for (int po = nxt[u]; po > 0; po = nxt[po]) {
    if (lvl[dir[po]] == lvl[u] + 1 && cost[po]) {
      int x = DFS(dir[po], min(w, cost[po]));
      w -= x;
      cost[po] -= x;
      cost[rev[po]] += x;
    }
  }
  if (w == flow) lvl[u] = -3;
  return flow - w;
}
int MaxFlow() {
  int ans = 0;
  int p;
  while (BFS()) {
    while (p = DFS(s, 99999), p) {
      ans += p;
    }
  }
  return ans;
}
set<int> S;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (n); i++) nxt[i] = -1;
  h = n;
  for (int i = (1); i <= (n); i++) scanf("%d", &a[i]);
  for (int i = (1); i <= (m); i++) {
    scanf("%d%d", &l[i], &r[i]);
    insert(l[i], r[i]);
  }
  for (int i = (1); i <= (n); i++) visit[i] = 0;
  for (int i = (1); i <= (n); i++)
    if (visit[i] == 0) DFS2(i, 1);
  for (int i = (0); i <= (n + 1); i++) nxt[i] = -1;
  h = n + 1;
  for (int i = (1); i <= (n); i++) {
    if (c[i] == 1)
      insert2(i, n + 1, i);
    else
      insert2(0, i, i);
  }
  for (int i = (1); i <= (m); i++) {
    if (c[l[i]] == 1)
      insert2(r[i], l[i], 0);
    else
      insert2(l[i], r[i], 0);
  }
  for (int i = (1); i <= (n); i++) {
    int base = a[i];
    for (int j = (2); j <= (sqrt(base)); j++) {
      if (base % j == 0) {
        S.insert(j);
        while (base % j == 0) base /= j;
      }
    }
    if (base != 1) S.insert(base);
  }
  int ans = 0;
  s = 0;
  t = n + 1;
  for (set<int>::iterator it = S.begin(); it != S.end(); ++it) {
    int w = *it;
    for (int i = (1); i <= (h); i++) cost[i] = 0;
    for (int i = (1); i <= (h); i++)
      if (ty[i] == 0) cost[i] = 999;
    for (int i = (1); i <= (n); i++) {
      b[i] = 0;
      int base = a[i];
      while (base % w == 0) {
        base /= w;
        b[i]++;
      }
      cost[edge[i]] = b[i];
    }
    ans += MaxFlow();
  }
  printf("%d\n", ans);
  return 0;
}
