#include <bits/stdc++.h>
using namespace std;
const long long INF = numeric_limits<long long>::max() / 4;
struct Edge {
  long long from, to, cap, flow, index;
  Edge(long long from, long long to, long long cap, long long flow,
       long long index)
      : from(from), to(to), cap(cap), flow(flow), index(index) {}
  long long rcap() { return cap - flow; }
};
struct Dinic {
  long long N;
  vector<vector<Edge> > G;
  vector<vector<Edge *> > Lf;
  vector<long long> layer;
  vector<long long> Q;
  Dinic(long long N) : N(N), G(N), Q(N) {}
  void AddEdge(long long from, long long to, long long cap) {
    if (from == to) return;
    G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
    G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
  }
  long long BlockingFlow(long long s, long long t) {
    layer.clear();
    layer.resize(N, -1);
    layer[s] = 0;
    Lf.clear();
    Lf.resize(N);
    long long head = 0, tail = 0;
    Q[tail++] = s;
    while (head < tail) {
      long long first = Q[head++];
      for (long long i = 0; i < G[first].size(); i++) {
        Edge &e = G[first][i];
        if (e.rcap() <= 0) continue;
        if (layer[e.to] == -1) {
          layer[e.to] = layer[e.from] + 1;
          Q[tail++] = e.to;
        }
        if (layer[e.to] > layer[e.from]) {
          Lf[e.from].push_back(&e);
        }
      }
    }
    if (layer[t] == -1) return 0;
    long long totflow = 0;
    vector<Edge *> P;
    while (!Lf[s].empty()) {
      long long curr = P.empty() ? s : P.back()->to;
      if (curr == t) {
        long long amt = P.front()->rcap();
        for (long long i = 0; i < P.size(); ++i) {
          amt = min(amt, P[i]->rcap());
        }
        totflow += amt;
        for (long long i = P.size() - 1; i >= 0; --i) {
          P[i]->flow += amt;
          G[P[i]->to][P[i]->index].flow -= amt;
          if (P[i]->rcap() <= 0) {
            Lf[P[i]->from].pop_back();
            P.resize(i);
          }
        }
      } else if (Lf[curr].empty()) {
        P.pop_back();
        for (long long i = 0; i < N; ++i)
          for (long long j = 0; j < Lf[i].size(); ++j)
            if (Lf[i][j]->to == curr) Lf[i].erase(Lf[i].begin() + j);
      } else {
        P.push_back(Lf[curr].back());
      }
    }
    return totflow;
  }
  long long GetMaxFlow(long long s, long long t) {
    long long totflow = 0;
    while (long long flow = BlockingFlow(s, t)) totflow += flow;
    return totflow;
  }
};
long long N, M;
set<long long> pr;
set<long long>::iterator it;
long long a[157], b[157];
pair<long long, long long> E[157];
long long get(long long p, long long N) {
  memset(b, 0, sizeof(b));
  for (long long i = (1); i < (N + 1); i++) {
    while (a[i] % p == 0) {
      b[i]++;
      a[i] /= p;
    }
  }
  Dinic F(N + 7);
  for (long long i = 1; i <= N; i += 2) {
    F.AddEdge(0, i, b[i]);
  }
  for (long long i = 2; i <= N; i += 2) {
    F.AddEdge(i, N + 1, b[i]);
  }
  for (long long i = (0); i < (M); i++) {
    F.AddEdge(E[i].first, E[i].second, min(b[E[i].first], b[E[i].second]));
  }
  return F.GetMaxFlow(0, N + 1);
}
int main() {
  scanf("%lld %lld", &N, &M);
  for (long long i = (1); i < (N + 1); i++) {
    scanf("%lld", &a[i]);
  }
  for (long long i = (0); i < (M); i++) {
    scanf("%lld %lld", &E[i].first, &E[i].second);
    if (E[i].first % 2 == 0) swap(E[i].first, E[i].second);
  }
  for (long long i = (1); i < (N + 1); i++) {
    long long tmp = a[i];
    if (tmp % 2 == 0) {
      pr.insert(2);
      while (tmp % 2 == 0) {
        tmp /= 2;
      }
    }
    for (long long j = 3; j * j <= tmp; j += 2) {
      if (tmp % j == 0) {
        pr.insert(j);
        while (tmp % j == 0) {
          tmp /= j;
        }
      }
    }
    if (tmp > 1) pr.insert(tmp);
  }
  long long ans = 0;
  for (it = pr.begin(); it != pr.end(); it++) {
    ans += get(*it, N);
  }
  printf("%lld\n", ans);
}
