#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > nodefac[101];
struct edge {
  int f, t, nxt, cost;
  edge(int f, int t, int nxt, int cost) : f(f), t(t), nxt(nxt), cost(cost) {}
};
int head[4001];
int lastedge, lastnode;
vector<edge> edges;
void addEdge(int f, int t, int c) {
  edge tmp(f, t, head[f], c);
  head[f] = lastedge++;
  edges.push_back(tmp);
}
void Factorize(int num, int node) {
  int k = ceil(sqrt(num));
  for (int i = 2; i <= k; i++) {
    while (num % i == 0) {
      lastnode++;
      nodefac[node].push_back(make_pair(i, lastnode));
      num /= i;
    }
  }
  if (num != 1) {
    nodefac[node].push_back(make_pair(num, ++lastnode));
  }
}
int vis[101];
void adjust_graph() {
  for (int i = 1; i <= 100; i++)
    if (vis[i]) {
      if (i % 2) {
        for (int j = 0; j < nodefac[i].size(); j++) {
          addEdge(nodefac[i][j].second, 3500, 1);
          addEdge(3500, nodefac[i][j].second, 0);
        }
      } else {
        for (int j = 0; j < nodefac[i].size(); j++) {
          addEdge(0, nodefac[i][j].second, 1);
          addEdge(nodefac[i][j].second, 0, 0);
        }
      }
    }
}
int parent[4000];
bool BFS() {
  queue<int> bfsq;
  bfsq.push(0);
  int vis[3501];
  memset(vis, 0, sizeof vis);
  while (bfsq.size()) {
    int sz = bfsq.size();
    while (sz--) {
      int cur = bfsq.front();
      bfsq.pop();
      for (int i = head[cur]; i != -1; i = edges[i].nxt) {
        if (edges[i].cost && !vis[edges[i].t]) {
          vis[edges[i].t] = true;
          bfsq.push(edges[i].t);
          parent[edges[i].t] = i;
          if (edges[i].t == 3500) return 1;
        }
      }
    }
  }
  return 0;
}
int maxflow(int src, int snc) {
  int ret = 0;
  while (BFS()) {
    ret++;
    for (int i = 3500; i != 0; i = edges[parent[i]].f) {
      edges[parent[i]].cost--;
      edges[parent[i] ^ 1].cost++;
    }
  }
  return ret;
}
int main() {
  memset(head, -1, sizeof head);
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    int tmp;
    scanf("%d", &tmp);
    Factorize(tmp, i + 1);
  }
  for (int i = 0; i < m; i++) {
    int arr[2], a, b;
    scanf("%d%d", &a, &b);
    arr[a % 2] = a;
    arr[b % 2] = b;
    vis[a] = vis[b] = 1;
    for (int j = 0; j < nodefac[arr[0]].size(); j++)
      for (int k = 0; k < nodefac[arr[1]].size(); k++) {
        if (nodefac[arr[0]][j].first == nodefac[arr[1]][k].first) {
          addEdge(nodefac[arr[0]][j].second, nodefac[arr[1]][k].second, 1);
          addEdge(nodefac[arr[1]][k].second, nodefac[arr[0]][j].second, 0);
        }
      }
  }
  adjust_graph();
  cout << maxflow(0, 3500) << endl;
  return 0;
}
