#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5;
int n, m, a[N], nv;
pair<int, int> good[N];
bool isg[N][N];
vector<vector<int> > al;
vector<int> refer, match;
vector<bool> mark;
bool dfs(int v) {
  if (mark[v]) return false;
  mark[v] = true;
  for (auto &u : al[v]) {
    if (match[u] == -1 || dfs(match[u]))
      return match[v] = u, match[u] = v, true;
  }
  return false;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", a + i);
  memset(isg, false, sizeof isg);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--;
    y--;
    isg[x][y] = isg[y][x] = true;
  }
  map<int, vector<pair<int, int> > > mp;
  for (int i = 0; i < n; i++) {
    int x = a[i];
    for (int j = 2; j * j <= x; j++) {
      if (x % j) continue;
      int cnt = 0;
      while (x % j == 0) {
        x /= j;
        cnt++;
      }
      mp[j].push_back(pair<int, int>(i, cnt));
    }
    if (x > 1) mp[x].push_back(pair<int, int>(i, 1));
  }
  nv = 0;
  for (auto it = mp.begin(); it != mp.end(); it++) {
    int nv1 = nv;
    vector<pair<int, int> > &vv = it->second;
    for (int j = 0; j < vv.size(); j++) {
      for (int k = 0; k < vv[j].second; k++) {
        al.push_back(vector<int>());
        refer.push_back(vv[j].first);
      }
      nv += vv[j].second;
    }
    for (int i = nv1; i < nv; i++)
      for (int j = nv1 + 1; j < nv; j++)
        if (isg[refer[i]][refer[j]]) {
          if (refer[i] & 1)
            al[i].push_back(j);
          else
            al[j].push_back(i);
        }
  }
  match.assign(nv, -1);
  while (true) {
    mark.assign(nv, false);
    bool fnd = false;
    for (int i = 0; i < nv; i++)
      if (match[i] == -1 && !mark[i]) fnd |= dfs(i);
    if (!fnd) break;
  }
  int ans = 0;
  for (int i = 0; i < nv; i++) {
    if (match[i] != -1) ans++;
  }
  cout << ans / 2 << "\n";
  return 0;
}
