#include <bits/stdc++.h>
using namespace std;
struct maxFlow {
  struct Edge {
    int x, y;
    int cap, flow;
  };
  int N;
  maxFlow(int _N) : N(_N) {}
  int visited[1000], prev[1000];
  vector<Edge> E;
  vector<int> g[1000];
  void addEdge(int x, int y, int cap) {
    Edge e1 = {x, y, cap, 0}, e2 = {y, x, 0, 0};
    g[x].push_back(E.size());
    E.push_back(e1);
    g[y].push_back(E.size());
    E.push_back(e2);
  }
  bool bfs(int s, int t) {
    int x, y;
    for (int i = 1; i <= N; i++) visited[i] = prev[i] = -1;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      x = q.front();
      q.pop();
      visited[x] = 1;
      for (__typeof(g[x].begin()) it(g[x].begin()); it != g[x].end(); it++) {
        Edge &e = E[*it];
        y = e.y;
        if (e.cap == 0 or visited[y] == 1) continue;
        visited[y] = 1, prev[y] = *it;
        q.push(y);
      }
    }
    return (visited[t] == 1);
  }
  int maxflow(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
      int cap = (1 << 29);
      for (int i = t; i != s; i = E[prev[i]].x) cap = min(cap, E[prev[i]].cap);
      for (int i = t; i != s; i = E[prev[i]].x)
        E[prev[i]].cap -= cap, E[prev[i] ^ 1].cap += cap;
      ans += cap;
    }
    return ans;
  }
};
int n, m, a[101], res;
set<int> primes;
int gp[101][101];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    int tmp = a[i];
    for (int j = 2; j * j <= tmp; j++) {
      if (tmp % j == 0) {
        primes.insert(j);
        while (tmp % j == 0) tmp /= j;
      }
    }
    if (tmp > 1) primes.insert(tmp);
  }
  int S = n + 1, T = n + 2;
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    gp[x][y] = gp[y][x] = 1;
  }
  for (__typeof(primes.begin()) pp(primes.begin()); pp != primes.end(); pp++) {
    maxFlow mf(n + 2);
    int p = *pp;
    for (int i = 1; i <= n; i++) {
      int cnt = 0, tmp = a[i];
      while (tmp % p == 0) cnt++, tmp /= p;
      if (i % 2 == 1)
        mf.addEdge(S, i, cnt);
      else
        mf.addEdge(i, T, cnt);
    }
    for (int i = 1; i <= n; i += 2) {
      if (a[i] % p != 0) continue;
      int tmp = a[i], cnt2 = 0;
      while (tmp % p == 0) cnt2++, tmp /= p;
      for (int j = 2; j <= n; j += 2) {
        if (a[j] % p != 0 or !gp[i][j]) continue;
        int cnt = 0;
        tmp = a[j];
        while (tmp % p == 0) cnt++, tmp /= p;
        mf.addEdge(i, j, min(cnt, cnt2));
      }
    }
    res += mf.maxflow(S, T);
  }
  printf("%d\n", res);
  return 0;
}
