#include <bits/stdc++.h>
using namespace std;
vector<int> G[100001];
int n, m, match[100001], dist[100001];
bool bfs() {
  int i, u, v, len;
  queue<int> Q;
  for (i = 1; i <= n; i++) {
    if (match[i] == 0) {
      dist[i] = 0;
      Q.push(i);
    } else
      dist[i] = (1 << 28);
  }
  dist[0] = (1 << 28);
  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    if (u != 0) {
      len = G[u].size();
      for (i = 0; i < len; i++) {
        v = G[u][i];
        if (dist[match[v]] == (1 << 28)) {
          dist[match[v]] = dist[u] + 1;
          Q.push(match[v]);
        }
      }
    }
  }
  return (dist[0] != (1 << 28));
}
bool dfs(int u) {
  int i, v, len;
  if (u != 0) {
    len = G[u].size();
    for (i = 0; i < len; i++) {
      v = G[u][i];
      if (dist[match[v]] == dist[u] + 1) {
        if (dfs(match[v])) {
          match[v] = u;
          match[u] = v;
          return true;
        }
      }
    }
    dist[u] = (1 << 28);
    return false;
  }
  return true;
}
int hopcroft_karp() {
  int matching = 0, i;
  while (bfs())
    for (i = 1; i <= n; i++)
      if (match[i] == 0 && dfs(i)) matching++;
  return matching;
}
vector<int> prime(int n) {
  vector<int> ret;
  for (int i = 2; i * i <= n; i++)
    while (n % i == 0) ret.push_back(i), n /= i;
  if (n > 1) ret.push_back(n);
  return ret;
}
int a[100005];
pair<int, int> good[100005];
vector<pair<int, int>> grp[100005];
int main() {
  int v, q;
  cin >> v >> q;
  for (int i = 1; i <= v; i++) {
    cin >> a[i];
  }
  n = 0, m = 0;
  for (int i = 1; i <= v; i++) {
    if (i % 2 == 1) {
      vector<int> tmp = prime(a[i]);
      for (int j = 0; j < tmp.size(); j++) {
        grp[i].push_back({tmp[j], ++n});
      }
    }
  }
  for (int i = 1; i <= v; i++) {
    if (i % 2 == 0) {
      vector<int> tmp = prime(a[i]);
      for (int j = 0; j < tmp.size(); j++) {
        grp[i].push_back({tmp[j], ++m + n});
      }
    }
  }
  int x, y;
  while (q--) {
    cin >> x >> y;
    for (auto i : grp[x]) {
      for (auto j : grp[y]) {
        if (i.first == j.first) {
          G[i.second].push_back(j.second);
          G[j.second].push_back(i.second);
        }
      }
    }
  }
  printf("%d\n", hopcroft_karp());
  return 0;
}
