#include <bits/stdc++.h>
using namespace std;
bool debug;
const int inf = 1e9 + 5;
const int nax = 1e3 + 5;
namespace Flow {
int odl[nax], q[nax];
int m[nax][nax];
vector<int>::iterator pocz[nax];
vector<int> v[nax];
void init(int n) {
  for (int i = 0; i <= n; ++i) v[i].clear();
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= n; ++j) m[i][j] = 0;
}
void AddEdge(int a, int b, int c) {
  v[a].push_back(b);
  v[b].push_back(a);
  m[a][b] += c;
}
bool bst(int s, int t, int n) {
  for (int i = 0; i <= n; ++i) odl[i] = inf;
  odl[s] = 0;
  int qbeg = 0, qend = 0;
  q[qend++] = s;
  while (qbeg < qend) {
    int x = q[qbeg++];
    for (auto j : v[x])
      if (m[x][j] > 0 && odl[j] == inf) {
        odl[j] = odl[x] + 1;
        q[qend++] = j;
      }
  }
  return odl[t] != inf;
}
int flow(int x, int t, int maximum) {
  if (x == t || maximum == 0) return maximum;
  int res = 0;
  for (vector<int>::iterator &it = pocz[x]; it != v[x].end(); it++)
    if (m[x][*it] > 0 && odl[*it] == odl[x] + 1) {
      int y = flow(*it, t, min(maximum, m[x][*it]));
      maximum -= y;
      m[x][*it] -= y;
      m[*it][x] += y;
      res += y;
      if (maximum == 0) return res;
    }
  return res;
}
int MaxFlow(int s, int t, int n) {
  int res = 0;
  while (bst(s, t, n)) {
    for (int i = 0; i <= n; ++i) pocz[i] = v[i].begin();
    res += flow(s, t, inf);
  }
  return res;
}
}  // namespace Flow
int n, m, c, d;
int a[nax], pocz[nax];
vector<pair<int, int> > fac[nax];
int main(int argc, char *argv[]) {
  debug = argc > 1;
  scanf("%d%d", &n, &m);
  int indeks = 1;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    pocz[i] = indeks;
    for (int j = 2; j * j <= a[i]; j++)
      if (a[i] % j == 0) {
        int ile = 0;
        while (a[i] % j == 0) {
          a[i] /= j;
          ++ile;
        }
        fac[i].push_back(make_pair(j, ile));
        ++indeks;
      }
    if (a[i] > 1) {
      fac[i].push_back(make_pair(a[i], 1));
      ++indeks;
    }
  }
  Flow::init(indeks + 1);
  for (int i = 1; i <= n; ++i) {
    int dl = (int)fac[i].size();
    for (int j = 0; j <= (dl)-1; ++j)
      if (i & 1)
        Flow::AddEdge(pocz[i] + j, indeks + 1, fac[i][j].second);
      else
        Flow::AddEdge(0, pocz[i] + j, fac[i][j].second);
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &c, &d);
    if (c & 1) swap(c, d);
    int dl1 = (int)fac[c].size();
    int dl2 = (int)fac[d].size();
    for (int j = 0; j <= (dl1)-1; ++j)
      for (int k = 0; k <= (dl2)-1; ++k)
        if (fac[c][j].first == fac[d][k].first)
          Flow::AddEdge(pocz[c] + j, pocz[d] + k, inf);
  }
  printf("%d\n", Flow::MaxFlow(0, indeks + 1, indeks + 1));
  return 0;
}
