#include <bits/stdc++.h>
using namespace std;
struct dinic {
  struct edge {
    size_t src, dst, rev;
    int flow, cap;
  };
  int n;
  vector<vector<edge> > adj;
  dinic(int n) : n(n), adj(n), level(n), q(n), it(n) {}
  void add_edge(size_t src, size_t dst, int cap, int rcap = 0) {
    edge e1;
    e1.src = src;
    e1.dst = dst;
    e1.rev = adj[dst].size();
    e1.flow = 0;
    e1.cap = cap;
    adj[src].push_back(e1);
    if (src == dst) adj[src].back().rev++;
    edge e2;
    e2.src = dst;
    e2.dst = src;
    e2.rev = adj[src].size() - 1;
    e2.flow = 0;
    e2.cap = rcap;
    adj[dst].push_back(e2);
  }
  vector<int> level, q, it;
  bool bfs(int source, int sink) {
    fill(level.begin(), level.end(), -1);
    for (int qf = level[q[0] = sink] = 0, qb = 1; qf < qb; ++qf) {
      sink = q[qf];
      for (int i = 0; i < adj[sink].size(); ++i) {
        edge &e = adj[sink][i];
        edge &r = adj[e.dst][e.rev];
        if (r.flow < r.cap && level[e.dst] == -1)
          level[q[qb++] = e.dst] = 1 + level[sink];
      }
    }
    return level[source] != -1;
  }
  int augment(int source, int sink, int flow) {
    if (source == sink) return flow;
    for (; it[source] != adj[source].size(); ++it[source]) {
      edge &e = adj[source][it[source]];
      if (e.flow < e.cap && level[e.dst] + 1 == level[source]) {
        int delta = augment(e.dst, sink, min(flow, e.cap - e.flow));
        if (delta > 0) {
          e.flow += delta;
          adj[e.dst][e.rev].flow -= delta;
          return delta;
        }
      }
    }
    return 0;
  }
  int max_flow(int source, int sink) {
    for (int u = 0; u < n; ++u)
      for (int i = 0; i < adj[u].size(); ++i) {
        edge &e = adj[u][i];
        e.flow = 0;
      }
    int flow = 0;
    int oo = numeric_limits<int>::max();
    while (bfs(source, sink)) {
      fill(it.begin(), it.end(), 0);
      for (int f; (f = augment(source, sink, oo)) > 0;) flow += f;
    }
    return flow;
  }
};
long long sieve_size;
bitset<100000010> bs;
vector<int> primes;
void sieve(long long upperbound) {
  sieve_size = upperbound;
  bs.set();
  bs[0] = bs[1] = 0;
  for (long long i = 2; i <= sieve_size; ++i)
    if (bs[i]) {
      for (long long j = i * i; j <= sieve_size; j += i) bs[j] = 0;
      primes.push_back(i);
    }
}
vector<int> primefactors(long long n) {
  vector<int> factors;
  long long PF_idx = 0, PF = primes[PF_idx];
  while (PF * PF <= n) {
    while (n % PF == 0) {
      n /= PF;
      factors.push_back(PF);
    }
    PF = primes[++PF_idx];
  }
  if (n != 1) factors.push_back(n);
  return factors;
}
long long nums[110];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  sieve(1000000);
  for (int i = 1; i <= n; ++i) cin >> nums[i];
  struct dinic d(100000);
  int x, y;
  vector<int> factorsX;
  vector<int> factorsY;
  map<pair<pair<int, int>, int>, int> f;
  int s = 0;
  int t = 1;
  int vertex1 = 2;
  int vertex2 = n * n;
  for (int j = 1; j <= m; ++j) {
    cin >> x >> y;
    if (x % 2 == 0) swap(x, y);
    factorsX.clear();
    factorsY.clear();
    factorsX = primefactors(nums[x]);
    factorsY = primefactors(nums[y]);
    for (int i = 0; i < factorsX.size(); ++i) {
      if (f.find(make_pair(pair<int, int>(x, i), factorsX[i])) == f.end()) {
        f[make_pair(pair<int, int>(x, i), factorsX[i])] = vertex1++;
      }
    }
    for (int i = 0; i < factorsY.size(); ++i) {
      if (f.find(make_pair(pair<int, int>(y, i), factorsY[i])) == f.end()) {
        f[make_pair(pair<int, int>(y, i), factorsY[i])] = vertex2++;
      }
    }
    for (int i = 0; i < factorsX.size(); ++i) {
      int factX = factorsX[i];
      for (int j = 0; j < factorsY.size(); ++j) {
        int factY = factorsY[j];
        if (factX == factY) {
          int source = f[make_pair(pair<int, int>(x, i), factorsX[i])];
          int dest = f[make_pair(pair<int, int>(y, j), factorsY[j])];
          d.add_edge(source, dest, 1);
        }
      }
    }
  }
  for (int i = 2; i < vertex1; ++i) {
    d.add_edge(s, i, 1);
  }
  for (int i = n * n; i < vertex2; ++i) {
    d.add_edge(i, t, 1);
  }
  int mf = d.max_flow(s, t);
  cout << mf << '\n';
}
