#include <bits/stdc++.h>
using namespace std;
const int N = 150;
const int INF = 0x3FFFFFFF;
struct Dinic {
  struct Edge {
    int v, c, r;
  };
  int n;
  vector<Edge> E[N];
  int dis[N];
  int dfs(int u, int rem) {
    if (u == n - 1 || rem == 0) return rem;
    int res = 0;
    for (Edge &e : E[u]) {
      if (e.c > 0 && dis[e.v] == dis[u] + 1) {
        int tmp = dfs(e.v, min(rem, e.c));
        res += tmp, rem -= tmp;
        e.c -= tmp;
        E[e.v][e.r].c += tmp;
      }
    }
    return res == 0 ? dis[u] = res : res;
  }
  int bfs() {
    for (int i = 0; i < n; i++) dis[i] = INF;
    dis[0] = 0;
    queue<int> q;
    for (q.push(0); !q.empty(); q.pop()) {
      int u = q.front();
      for (Edge &e : E[u]) {
        if (e.c > 0 && dis[e.v] == INF) {
          dis[e.v] = dis[u] + 1;
          q.push(e.v);
        }
      }
    }
    return dis[n - 1] != INF;
  }
  int sol() {
    int res = 0, tmp;
    while (bfs()) {
      while ((tmp = dfs(0, INF)) > 0) res += tmp;
    }
    return res;
  }
  void add(int u, int v, int c) {
    E[u].push_back({v, c, (int)E[v].size()});
    E[v].push_back({u, 0, (int)E[u].size() - 1});
  }
};
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<long long> a(n + 1);
  vector<map<long long, int>> M(n + 1);
  set<long long> S;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    for (long long j = 2; j * j <= a[i]; j++) {
      if (a[i] % j == 0) {
        S.insert(j);
        while (a[i] % j == 0) {
          M[i][j]++;
          a[i] /= j;
        }
      }
    }
    if (a[i] > 1) S.insert(a[i]), M[i][a[i]]++;
  }
  int ans = 0;
  Dinic D;
  D.n = 1 + n + 1;
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d%d", &u, &v);
    if (v & 1) swap(u, v);
    D.add(u, v, INF);
  }
  for (int p : S) {
    Dinic DD = D;
    for (int i = 1; i <= n; i++) {
      if (i & 1)
        DD.add(0, i, M[i][p]);
      else
        DD.add(i, DD.n - 1, M[i][p]);
    }
    ans += DD.sol();
  }
  printf("%d\n", ans);
}
