#include <bits/stdc++.h>
using namespace std;
long long Set(long long n, long long pos) { return n | (1LL << pos); }
bool Check(long long n, long long pos) { return (bool)(n & (1LL << pos)); }
const int MaxLeftNodes = 50000;
const int MaxRightNodes = 50000;
const int MaxEdges = 150000;
int LeftNodesNo, RightNodesNo, edges;
int last[MaxLeftNodes], previous[MaxEdges], to[MaxEdges];
int matching[MaxRightNodes], dist[MaxLeftNodes], Q[MaxLeftNodes];
bool used[MaxLeftNodes], vis[MaxLeftNodes];
void init(int _LeftNodesNo, int _RightNodesNo) {
  LeftNodesNo = _LeftNodesNo;
  RightNodesNo = _RightNodesNo;
  edges = 0;
  fill(last, last + LeftNodesNo + 1, -1);
}
void add_edge(int u, int v) {
  to[edges] = v;
  previous[edges] = last[u];
  last[u] = edges++;
}
void bfs() {
  fill(dist, dist + LeftNodesNo + 1, -1);
  int QueueSize = 0;
  for (int u = 1; u <= LeftNodesNo; ++u) {
    if (used[u] == 0) {
      Q[QueueSize++] = u;
      dist[u] = 0;
    }
  }
  for (int i = 0; i < QueueSize; i++) {
    int u1 = Q[i];
    for (int e = last[u1]; e >= 0; e = previous[e]) {
      int u2 = matching[to[e]];
      if (u2 >= 0 && dist[u2] < 0) {
        dist[u2] = dist[u1] + 1;
        Q[QueueSize++] = u2;
      }
    }
  }
}
bool dfs(int u1) {
  vis[u1] = 1;
  for (int e = last[u1]; e >= 0; e = previous[e]) {
    int v = to[e];
    int u2 = matching[v];
    if (u2 < 0 || vis[u2] == 0 && dist[u2] == dist[u1] + 1 && dfs(u2)) {
      matching[v] = u1;
      used[u1] = 1;
      return 1;
    }
  }
  return 0;
}
long long bpm() {
  fill(used, used + LeftNodesNo + 1, 0);
  fill(matching, matching + RightNodesNo + 1, -1);
  for (long long res = 0;;) {
    bfs();
    fill(vis, vis + LeftNodesNo + 1, 0);
    int f = 0;
    for (int u = 1; u <= LeftNodesNo; ++u)
      if (used[u] == 0 && dfs(u)) ++f;
    if (f == 0) return res;
    res += f;
  }
}
long long od, ev;
vector<pair<long long, long long> > vec[110];
int main() {
  long long cs, ts, i, j, k, x, y, z, q, m, n;
  while (scanf("%lld", &n) != EOF) {
    scanf("%lld", &m);
    od = 0, ev = 0;
    for (i = 1; i <= n; i++) {
      scanf("%lld", &x);
      for (j = 2; j * j <= x; j++) {
        while (x % j == 0) {
          x /= j;
          if (i & 1)
            vec[i].push_back(pair<long long, long long>(j, ++od));
          else
            vec[i].push_back(pair<long long, long long>(j, ++ev));
        }
      }
      if (x != 1) {
        if (i & 1)
          vec[i].push_back(pair<long long, long long>(x, ++od));
        else
          vec[i].push_back(pair<long long, long long>(x, ++ev));
      }
    }
    init(od, ev);
    for (i = 1; i <= m; i++) {
      scanf("%lld", &x);
      scanf("%lld", &y);
      if (y & 1) {
        swap(x, y);
      }
      for (j = 0; j < vec[x].size(); j++)
        for (k = 0; k < vec[y].size(); k++) {
          if (vec[x][j].first == vec[y][k].first) {
            add_edge(vec[x][j].second, vec[y][k].second);
          }
        }
    }
    printf("%lld\n", bpm());
  }
  return 0;
}
