#include <bits/stdc++.h>
using namespace std;
bool debug = false;
namespace Dinic {
struct Edge {
  int to;
  int val;
  int rev;
  Edge(int a, int b, int c) {
    to = a;
    val = b;
    rev = c;
  }
};
vector<Edge> nei[105];
int lv[105];
int iter[105];
void addEdge(int from, int to, int val) {
  nei[from].push_back(Edge(to, val, nei[to].size()));
  nei[to].push_back(Edge(from, 0, nei[from].size() - 1));
}
void bfs(int s) {
  memset(lv, -1, sizeof(lv));
  queue<int> q;
  q.push(s);
  lv[s] = 0;
  while (!q.empty()) {
    int last = q.front();
    q.pop();
    for (Edge x : nei[last]) {
      if (lv[x.to] == -1 && x.val > 0) {
        lv[x.to] = lv[last] + 1;
        q.push(x.to);
      }
    }
  }
}
int dfs(int s, int t, int f) {
  if (s == t) {
    return f;
  }
  for (int& i = iter[s]; i < nei[s].size(); i++) {
    Edge& e = nei[s][i];
    if (e.val > 0 && lv[e.to] > lv[s]) {
      int d = dfs(e.to, t, min(f, e.val));
      if (d > 0) {
        e.val -= d;
        nei[e.to][e.rev].val += d;
        return d;
      }
    }
  }
  return 0;
}
int getMaxflow(int s, int t) {
  int flow = 0;
  while (true) {
    bfs(s);
    if (lv[t] == -1) {
      return flow;
    }
    memset(iter, 0, sizeof(iter));
    int f;
    while ((f = dfs(s, t, 1e9)) != 0) {
      flow += f;
    }
  }
}
}  // namespace Dinic
int n, m;
int a[105];
vector<int> nei[105];
map<int, int> f[105];
map<pair<int, int>, int> id;
void fact(int x) {
  int w = a[x];
  for (int i = 2; i * i <= w; i++) {
    if (w % i == 0) {
      while (w % i == 0) {
        w /= i;
        f[x][i]++;
      }
    }
  }
  if (w > 1) {
    f[x][w]++;
  }
}
int main(int argc, char* argv[]) {
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    nei[x].push_back(y);
    nei[y].push_back(x);
  }
  for (int i = 0; i < n; i++) {
    fact(i);
  }
  int ids = 0;
  for (int i = 0; i < n; i++) {
    for (auto j : f[i]) {
      id[make_pair(i, j.first)] = ids;
      ids++;
    }
  }
  int S = ids;
  ids++;
  int T = ids;
  ids++;
  for (int i = 0; i < n; i += 2) {
    for (auto j : f[i]) {
      Dinic::addEdge(S, id[make_pair(i, j.first)], j.second);
      for (int to : nei[i]) {
        if (id.count(make_pair(to, j.first))) {
          Dinic::addEdge(id[make_pair(i, j.first)], id[make_pair(to, j.first)],
                         1e9);
        }
      }
    }
  }
  for (int i = 1; i < n; i += 2) {
    for (auto j : f[i]) {
      Dinic::addEdge(id[make_pair(i, j.first)], T, j.second);
    }
  }
  cout << Dinic::getMaxflow(S, T);
  return 0;
}
