#include <bits/stdc++.h>
using namespace std;
const int MAXN = 7000;
const int INF = 1 << 29;
vector<int> G[MAXN];
int A, B, match[MAXN], dist[MAXN];
bool bfs() {
  queue<int> q;
  for (int i = 1; i < (int)A + 1; i++) {
    if (match[i] == 0) {
      dist[i] = 0;
      q.push(i);
    } else
      dist[i] = INF;
  }
  dist[0] = INF;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    if (v != 0) {
      for (int i = 0; i < (int)G[v].size(); i++) {
        int u = G[v][i];
        if (dist[match[u]] == INF) {
          dist[match[u]] = dist[v] + 1;
          q.push(match[u]);
        }
      }
    }
  }
  return (dist[0] != INF);
}
bool dfs(int v) {
  if (v != 0) {
    for (int i = 0; i < (int)G[v].size(); i++) {
      int u = G[v][i];
      if (dist[match[u]] == dist[v] + 1) {
        if (dfs(match[u])) {
          match[u] = v;
          match[v] = u;
          return true;
        }
      }
    }
    dist[v] = INF;
    return false;
  }
  return true;
}
int HK() {
  memset(match, 0, sizeof(match));
  int MBM = 0;
  while (bfs())
    for (int i = 1; i < (int)A + 1; i++)
      if (match[i] == 0 && dfs(i)) MBM++;
  return MBM;
}
const int MAXn = 103;
int a[MAXn], al[MAXn], ar[MAXn], n, m;
vector<int> AA, BB;
int main() {
  scanf("%d", &n), scanf("%d", &m);
  for (int i = 1; i < (int)n + 1; i++) {
    if (i & 1)
      al[i] = BB.size();
    else
      al[i] = AA.size();
    scanf("%d", &a[i]);
    int tmp = a[i], dd = 2;
    while (tmp > 1) {
      if (tmp % dd == 0) {
        if (i & 1)
          BB.push_back(dd);
        else
          AA.push_back(dd);
        tmp /= dd;
      } else
        dd++;
      if (dd * dd > a[i]) break;
    }
    if (tmp > 1) {
      if (i & 1)
        BB.push_back(tmp);
      else
        AA.push_back(tmp);
    }
    if (i & 1)
      ar[i] = BB.size();
    else
      ar[i] = AA.size();
  }
  A = AA.size();
  B = BB.size();
  for (int i = 0; i < (int)m; i++) {
    int e, o;
    scanf("%d", &e), scanf("%d", &o);
    if (e & 1) swap(e, o);
    for (int aa = al[e]; aa < (int)ar[e]; aa++)
      for (int bb = al[o]; bb < (int)ar[o]; bb++) {
        if (AA[aa] != BB[bb]) continue;
        G[aa + 1].push_back(bb + 1 + A);
      }
  }
  printf("%d\n", HK());
}
