#include <bits/stdc++.h>
using namespace std;
struct Graph {
  int n, et, ind[5011], e[61000], last[61000];
  inline void adde(int a, int b) {
    last[++et] = ind[a];
    e[et] = b;
    ind[a] = et;
  }
  inline void init(int nn) {
    n = nn, et = 1;
    memset(ind, 0, sizeof(int) * (n + 1));
  }
};
struct FlowGraph : public Graph {
  int S, T;
  int cap[61000], f[61000];
  inline void adde(int a, int b, int c) {
    Graph::adde(a, b);
    f[et] = 0, cap[et] = c;
  }
  inline void addee(int a, int b, int c) { adde(a, b, c), adde(b, a, c); }
  inline void init(int nn, int s, int t) {
    Graph::init(nn);
    S = s, T = t;
  }
};
struct ResiGraph : public FlowGraph {
  int ek[61000];
  bool checked[5011];
  void adde(int a, int b, int c, int k) {
    FlowGraph::adde(a, b, c);
    ek[et] = k;
  }
  int dfs(int a, int flow) {
    if (flow == 0) {
      return 0;
    }
    if (a == T) return flow;
    int ans = 0, now;
    for (int i = ind[a]; i; i = last[i])
      if (!checked[e[i]] && cap[i] - f[i]) {
        now = dfs(e[i], std::min(flow, cap[i] - f[i]));
        ans += now, f[i] += now, flow -= now;
      }
    if (flow) checked[a] = true;
    return ans;
  }
  int blocking_flow() {
    int upper_bound = 0;
    memset(checked, 0, sizeof(bool) * (n + 1));
    for (int i = ind[S]; i; i = last[i]) {
      upper_bound += cap[i];
    }
    return dfs(S, upper_bound);
  }
};
struct DinicGraph : public FlowGraph {
  ResiGraph resi;
  int que[5011], nowqt, qt, checked[5011];
  int cf() {
    resi.init(n, S, T);
    memset(checked, 0, sizeof(int) * (n + 1));
    qt = nowqt = 1;
    que[1] = S;
    checked[S] = 1;
    for (int i = 1, j = 0, nowlv = 2; i <= qt; i++) {
      if (i > nowqt) {
        nowlv++, nowqt = qt;
        if (checked[T]) {
          break;
        }
      }
      for (j = ind[que[i]]; j; j = last[j])
        if ((!checked[e[j]] || checked[e[j]] == nowlv) && f[j] < cap[j]) {
          if ((j & 1) && f[j ^ 1]) {
            resi.adde(que[i], e[j], f[j ^ 1], j);
            if (!checked[e[j]]) {
              que[++qt] = e[j];
              checked[e[j]] = nowlv;
            }
          } else if (!(j & 1)) {
            resi.adde(que[i], e[j], cap[j] - f[j], j);
            if (!checked[e[j]]) {
              que[++qt] = e[j];
              checked[e[j]] = nowlv;
            }
          }
        }
    }
    int incr = resi.blocking_flow();
    if (incr == 0) {
      return 0;
    }
    for (int i = 1, j, k; i <= n; i++) {
      for (j = resi.ind[i]; j; j = resi.last[j])
        if (resi.f[j]) {
          k = resi.ek[j];
          if (f[k ^ 1]) {
            f[k ^ 1] -= resi.f[j];
          } else {
            f[k] += resi.f[j];
          }
        }
    }
    return incr;
  }
  int maxflow() {
    int ans = 0, now = cf();
    while (now) {
      ans += now;
      now = cf();
    }
    return ans;
  }
} G;
int i, j, r, n, m;
int p[5011], q[5011][2];
int main() {
  scanf("%d %d", &n, &m);
  for (i = 1; i <= n; i++) {
    scanf("%d", &p[i]);
  }
  for (i = 1; i <= m; i++) {
    scanf("%d %d", &q[i][0], &q[i][1]);
    if (q[i][1] & 1) {
      swap(q[i][0], q[i][1]);
    }
  }
  int ans = 0;
  for (i = 2; i <= 10000; i++) {
    bool ok = false;
    for (j = 1; j <= n; j++)
      if (p[j] % i == 0) {
        ok = true;
        break;
      }
    if (!ok) {
      continue;
    }
    G.init(n + 2, n + 1, n + 2);
    for (j = 1; j <= n; j++) {
      int k = 0;
      while (p[j] % i == 0) {
        p[j] /= i;
        k++;
      }
      if (k) {
        if (j & 1) {
          G.addee(n + 1, j, k);
        } else {
          G.addee(j, n + 2, k);
        }
      }
    }
    for (j = 1; j <= m; j++) {
      G.addee(q[j][0], q[j][1], 100);
    }
    ans += G.maxflow();
  }
  for (r = 1; r <= n; r++)
    if (p[r] > 1) {
      i = p[r];
      G.init(n + 2, n + 1, n + 2);
      for (j = 1; j <= n; j++) {
        int k = 0;
        while (p[j] % i == 0) {
          p[j] /= i;
          k++;
        }
        if (k) {
          if (j & 1) {
            G.addee(n + 1, j, k);
          } else {
            G.addee(j, n + 2, k);
          }
        }
      }
      for (j = 1; j <= m; j++) {
        G.addee(q[j][0], q[j][1], 100);
      }
      ans += G.maxflow();
    }
  printf("%d\n", ans);
  return 0;
}
