#include <bits/stdc++.h>
using namespace std;
const double Pi = acos(-1.0);
const int MAXN = 1e6 + 5;
int n, m, t;
int v[MAXN];
struct Net {
  int s, t;
  int cnt;
  int head[MAXN], nxt[MAXN], to[MAXN], wei[MAXN];
  int depth[MAXN];
  int cur[MAXN];
  void init(int ss, int tt) {
    s = ss, t = tt;
    cnt = -1;
    memset(head, -1, sizeof(head));
    memset(nxt, -1, sizeof(nxt));
  }
  void addone(int u, int v, int w) {
    cnt++;
    nxt[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    wei[cnt] = w;
  }
  void add(int u, int v, int w) {
    addone(u, v, w);
    addone(v, u, 0);
  }
  int dfs(int u, int flow) {
    if (u == t) return flow;
    for (int& i = cur[u]; i != -1; i = nxt[i]) {
      if (depth[to[i]] == depth[u] + 1 && wei[i] != 0) {
        int dis = dfs(to[i], min(flow, wei[i]));
        if (dis > 0) {
          wei[i] -= dis, wei[i ^ 1] += dis;
          return dis;
        }
      }
    }
    return 0;
  }
  int bfs() {
    queue<int> q;
    memset(depth, 0, sizeof(depth));
    depth[s] = 1;
    q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int i = head[u]; i != -1; i = nxt[i]) {
        if (depth[to[i]] == 0 && wei[i] > 0) {
          depth[to[i]] = depth[u] + 1;
          q.push(to[i]);
        }
      }
    }
    return depth[t];
  }
  long long dinic() {
    long long ans = 0;
    while (bfs()) {
      for (int i = 1; i <= n + n; i++) cur[i] = head[i];
      while (int flow = dfs(s, 1e9)) ans += flow;
    }
    return ans;
  }
} net;
pair<int, int> e[MAXN];
int cnt[MAXN];
int main() {
  cin >> n >> m;
  set<int> se;
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
    int tmp = v[i];
    for (int j = 2; j * j <= tmp; j++) {
      while (tmp % j == 0) se.insert(j), tmp /= j;
    }
    if (tmp != 1) se.insert(tmp);
  }
  int ans = 0;
  for (int i = 1; i <= m; i++) {
    cin >> e[i].first >> e[i].second;
    if (e[i].first % 2) swap(e[i].first, e[i].second);
  }
  for (auto i : se) {
    for (int j = 1; j <= n; j++) {
      int sum = 0;
      int tmp = v[j];
      while (tmp % i == 0) tmp /= i, sum++;
      cnt[j] = sum;
    }
    net.init(n + 1, n + 2);
    for (int j = 1; j <= n; j++) {
      if (j % 2)
        net.add(j, n + 2, cnt[j]);
      else
        net.add(n + 1, j, cnt[j]);
    }
    for (int j = 1; j <= m; j++) {
      net.add(e[j].first, e[j].second, min(cnt[e[j].first], cnt[e[j].second]));
    }
    ans += net.dinic();
  }
  cout << ans;
}
