#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 * 20;
const long long INF = 1e16;
struct edge {
  int a, b;
  long long cap, flow;
};
int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
vector<edge> e;
vector<int> g[MAXN];
void add_edge(int a, int b, long long cap) {
  edge e1 = {a, b, cap, 0};
  edge e2 = {b, a, 0, 0};
  g[a].push_back((int)e.size());
  e.push_back(e1);
  g[b].push_back((int)e.size());
  e.push_back(e2);
}
bool bfs() {
  int qh = 0, qt = 0;
  q[qt++] = s;
  memset(d, -1, n * sizeof d[0]);
  d[s] = 0;
  while (qh < qt && d[t] == -1) {
    int v = q[qh++];
    for (size_t i = 0; i < g[v].size(); ++i) {
      int id = g[v][i], to = e[id].b;
      if (d[to] == -1 && e[id].flow < e[id].cap) {
        q[qt++] = to;
        d[to] = d[v] + 1;
      }
    }
  }
  return d[t] != -1;
}
long long dfs(int v, long long flow) {
  if (!flow) return 0;
  if (v == t) return flow;
  for (; ptr[v] < (int)g[v].size(); ++ptr[v]) {
    int id = g[v][ptr[v]], to = e[id].b;
    if (d[to] != d[v] + 1) continue;
    long long pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
    if (pushed) {
      e[id].flow += pushed;
      e[id ^ 1].flow -= pushed;
      return pushed;
    }
  }
  return 0;
}
long long dinic() {
  long long flow = 0;
  for (;;) {
    if (!bfs()) break;
    memset(ptr, 0, n * sizeof ptr[0]);
    long long pushed;
    while (pushed = dfs(s, INF)) flow += pushed;
  }
  return flow;
}
int from[111], to[111], numbers[111];
map<int, map<int, int> > index_to_vertex, count_v;
void generate_vertices(int x) {
  if (numbers[x] == 1) return;
  int tt = numbers[x];
  for (int j = 2; j * j <= tt; j++) {
    if (tt % j) continue;
    while (tt % j == 0) {
      tt /= j;
      count_v[x][j]++;
    }
    index_to_vertex[x][j] = n++;
  }
  if (tt > 1) {
    index_to_vertex[x][tt] = n++;
    count_v[x][tt]++;
  }
}
void print_vertices(int x) {
  cout << "Printing vertices for " << x << " (number " << numbers[x] << ")"
       << endl;
  for (const auto &p : index_to_vertex[x]) {
    cout << p.first << " " << count_v[x][p.first] << endl;
  }
}
int main() {
  int n0, m0;
  cin >> n0 >> m0;
  for (int i = 0; i < n0; i++) {
    cin >> numbers[i];
    generate_vertices(i);
  }
  for (int i = 0; i < m0; i++) {
    cin >> from[i] >> to[i];
    from[i]--;
    to[i]--;
    if (from[i] & 1) swap(from[i], to[i]);
    for (const auto &p : index_to_vertex[from[i]]) {
      int v = p.first;
      if (numbers[to[i]] % v) continue;
      add_edge(p.second, index_to_vertex[to[i]][v], INF);
    }
  }
  int sink = n++;
  int source = n++;
  for (int i = 0; i < n0; i++) {
    for (const auto &p : index_to_vertex[i]) {
      int vert = p.second;
      if (i & 1) {
        add_edge(vert, sink, count_v[i][p.first]);
      } else {
        add_edge(source, vert, count_v[i][p.first]);
      }
    }
  }
  s = source;
  t = sink;
  cout << dinic() << endl;
  return 0;
}
