#include <bits/stdc++.h>
using namespace std;
struct EDGES {
  int u, v, cap, flow, nextedge;
};
class MAXIMUM_FLOW {
 public:
  EDGES edge[100000];
  int n, m, level[100000], Prev[100000], last[100000];
  queue<int> Q;
  void init(int N) {
    n = N;
    m = -1;
    for (int j = 0; j <= n; j++) last[j] = -1;
  }
  void addedge(int a, int b, int c) {
    edge[++m].u = a, edge[m].v = b, edge[m].cap = c, edge[m].flow = 0,
    edge[m].nextedge = last[a], last[a] = m;
    edge[++m].u = b, edge[m].v = a, edge[m].cap = 0, edge[m].flow = 0,
    edge[m].nextedge = last[b], last[b] = m;
  }
  bool level_graph(int src, int snk) {
    for (int j = 0; j <= n; j++) level[j] = -1;
    int node, nxt;
    level[src] = 1;
    Q.push(src);
    while (!Q.empty()) {
      node = Q.front();
      Q.pop();
      for (int j = last[node]; j != -1; j = edge[j].nextedge) {
        nxt = edge[j].v;
        if (level[nxt] == -1 && edge[j].flow < edge[j].cap) {
          level[nxt] = level[node] + 1;
          Q.push(nxt);
        }
      }
    }
    return (level[snk] != -1);
  }
  int dfs(int node, int snk, int flow) {
    int nxt, curflow;
    if (node == snk) return flow;
    for (int &j = Prev[node]; j != -1; j = edge[j].nextedge) {
      nxt = edge[j].v;
      if (level[nxt] == level[node] + 1 && edge[j].flow < edge[j].cap) {
        curflow = dfs(nxt, snk, min(flow, edge[j].cap - edge[j].flow));
        if (curflow == 0) continue;
        edge[j].flow += curflow;
        edge[j ^ 1].flow -= curflow;
        return curflow;
      }
    }
    return 0;
  }
  int MAX_FLOW(int src, int snk) {
    int flow, ans = 0;
    while (level_graph(src, snk)) {
      for (int j = 0; j <= n; j++) Prev[j] = last[j];
      while (flow = dfs(src, snk, (1 << 31) - 1)) ans += flow;
    }
    return ans;
  }
} g;
int n, m, arr[105], node = 0;
map<int, int> times[105], num[105];
void calc(int i) {
  int x = arr[i];
  for (int j = 2; j * j <= x; ++j) {
    while (x % j == 0) {
      ++times[i][j];
      num[i][j];
      x /= j;
    }
  }
  if (x > 1) ++times[i][x], num[i][x];
  for (auto y : num[i]) num[i][y.first] = ++node;
}
int main() {
  cin >> n >> m;
  g.init(3500);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
    calc(i);
  }
  int src = ++node;
  int snk = ++node;
  for (int i = 0; i < n; i += 2) {
    for (auto y : times[i]) {
      int p = y.first;
      g.addedge(num[i][p], snk, y.second);
    }
  }
  for (int i = 1; i < n; i += 2) {
    for (auto y : times[i]) {
      int p = y.first;
      g.addedge(src, num[i][p], y.second);
    }
  }
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    if (u % 2 == 0) swap(u, v);
    for (auto y : num[u]) {
      int p = y.first;
      if (num[v].count(p)) {
        g.addedge(y.second, num[v][p], 40);
      }
    }
  }
  cout << g.MAX_FLOW(src, snk) << endl;
}
