#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1, -1, -1, 0, 1, -1, 0, 1};
int kx8[] = {1, 1, 2, 2, -1, -1, -2, -2};
int ky8[] = {2, -2, 1, -1, 2, -2, 1, -1};
const int M = 100005;
int n, m;
int rt[M], lf[M], vis[M], lvl[M];
vector<int> adj[M];
bool dfs(int x) {
  vis[x] = 1;
  for (auto y : adj[x]) {
    if (lf[y] == -1 || (!vis[lf[y]] && lvl[lf[y]] > lvl[x] && dfs(lf[y]))) {
      rt[x] = y;
      lf[y] = x;
      return true;
    }
  }
  return false;
}
long long hopcroft() {
  memset((rt), -1, sizeof(rt));
  memset((lf), -1, sizeof(lf));
  long long res = 0;
  while (true) {
    queue<int> q;
    memset((lvl), -1, sizeof(lvl));
    for (int i = 1; i <= n; i++) {
      if (rt[i] == -1) {
        lvl[i] = 0;
        q.push(i);
      } else {
        lvl[i] = -1;
      }
    }
    while (q.size()) {
      int x = q.front();
      q.pop();
      for (auto y : adj[x]) {
        if (lf[y] != -1 && lvl[lf[y]] == -1) {
          q.push(lf[y]);
          lvl[lf[y]] = lvl[x] + 1;
        }
      }
    }
    memset((vis), 0, sizeof(vis));
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
      if (rt[i] == -1 && dfs(i)) sum++;
    }
    if (!sum) break;
    res += sum;
  }
  for (int i = 0; i < (n + 2); i++) adj[i].clear();
  return res;
}
long long a[1005];
vector<int> v[1005], vv[1005];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  long long tot = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    long long sq = sqrt(a[i]);
    for (int j = 2; j <= sq; j++) {
      while (a[i] % j == 0) {
        a[i] /= j;
        v[i].push_back(j);
      }
    }
    if (a[i] != 1) v[i].push_back(a[i]);
    tot += v[i].size();
  }
  int cnt = 0, cn;
  for (int i = 2; i <= n; i += 2) {
    for (int j = 0; j < (v[i].size()); j++) vv[i].push_back(++cnt);
  }
  cn = cnt;
  for (int i = 1; i <= n; i += 2) {
    for (int j = 0; j < (v[i].size()); j++) vv[i].push_back(++cnt);
  }
  n = cn;
  while (m--) {
    int x, y;
    cin >> x >> y;
    if (x % 2) swap(x, y);
    for (int i = 0; i < v[x].size(); i++) {
      for (int j = 0; j < v[y].size(); j++) {
        if (v[x][i] == v[y][j]) adj[vv[x][i]].push_back(vv[y][j]);
      }
    }
  }
  cout << hopcroft() << endl;
  return 0;
}
