#include <bits/stdc++.h>
using namespace std;
template <class T>
int getbit(int i, T X) {
  return (X & (1 << (i - 1)));
}
template <class T>
T onbit(int i, T X) {
  return (X | (1 << (i - 1)));
}
template <class T>
T offbit(int i, T X) {
  return (X | (1 << (i - 1)) - (1 << (i - 1)));
}
template <class T>
T sqr(T x) {
  return (x * x);
}
template <class T>
T cube(T x) {
  return (x * x * x);
}
template <class T>
T gcd(T a, T b) {
  T r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
int csx[4] = {0, 0, -1, 1};
int csy[4] = {-1, 1, 0, 0};
const int MOD = 1000000007;
const int infi = 1e9;
const int maxn = 300;
const int maxv = 800;
struct Dinic {
  int n, s, t, E, adj[maxv + 5], next[maxv + 5], last[maxn + 5], run[maxv + 5],
      level[maxv + 5], que[maxv + 5], pre[maxv + 5];
  long long flow[maxv + 5], cap[maxv + 5];
  void init(int _n, int _s, int _t) {
    n = _n;
    s = _s;
    t = _t;
    E = 0;
    for (typeof(n) i = 0; i <= n; i++) last[i] = -1;
  }
  void add(int u, int v, long long c1, long long c2) {
    adj[E] = v;
    flow[E] = 0;
    cap[E] = c1;
    pre[E] = u;
    next[E] = last[u];
    last[u] = E++;
    adj[E] = u;
    flow[E] = 0;
    cap[E] = c2;
    pre[E] = v;
    next[E] = last[v];
    last[v] = E++;
  }
  bool bfs() {
    for (typeof(n) i = 0; i <= n; i++) level[i] = -1;
    level[s] = 0;
    int qsize = 0;
    que[qsize++] = s;
    for (typeof(qsize) i = 0; i < qsize; i++) {
      for (int u = que[i], e = last[u]; e != -1; e = next[e]) {
        int v = adj[e];
        if (flow[e] < cap[e] && level[v] == -1) {
          level[v] = level[u] + 1;
          que[qsize++] = v;
        }
      }
    }
    return level[t] != -1;
  }
  long long dfs(int u, long long bot) {
    if (u == t) return bot;
    for (int &e = run[u]; e != -1; e = next[e]) {
      int v = adj[e];
      long long delta = 0;
      if (level[v] == level[u] + 1 && flow[e] < cap[e] &&
          (delta = dfs(v, min(bot, cap[e] - flow[e] * 1ll))) > 0) {
        flow[e] += delta;
        flow[e ^ 1] -= delta;
        return delta;
      }
    }
    return 0;
  }
  long long maxFlow() {
    long long total = 0;
    while (bfs()) {
      for (typeof(n) i = 0; i <= n; i++) run[i] = last[i];
      for (int delta = dfs(s, infi); delta > 0; delta = dfs(s, infi))
        total += delta;
    }
    return total;
  }
};
int n, m, a[maxn + 5];
pair<int, long long> P[maxn + 5];
map<int, int> M[maxn + 5];
set<int> prime;
Dinic dinic;
void enter() {
  scanf("%d %d", &n, &m);
  for (typeof(n) i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (typeof(m) i = 1; i <= m; i++) scanf("%d %d", &P[i].first, &P[i].second);
}
void Phantich(int id, int n) {
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      int cnt = 0;
      while (n % i == 0) {
        cnt++;
        n /= i;
      }
      M[id][i] = cnt;
      prime.insert(i);
    }
  if (n > 1) {
    M[id][n] = 1;
    prime.insert(n);
  }
}
void solve() {
  for (typeof(n) i = 1; i <= n; i++) {
    Phantich(i, a[i]);
  }
  long long res = 0;
  for (typeof(prime.begin()) it = prime.begin(); it != prime.end(); it++) {
    dinic.init(n + 2, 0, n + 1);
    for (typeof(m) i = 1; i <= m; i++) {
      int u = P[i].first;
      int v = P[i].second;
      if (u % 2) swap(u, v);
      if ((M[u].find(*it) == M[u].end()) || (M[v].find(*it) == M[v].end()))
        continue;
      int c = min(M[u][*it], M[v][*it]);
      dinic.add(u, v, c, 0);
    }
    for (typeof(n) i = 1; i <= n; i++)
      if (i % 2 == 0) {
        if (M[i].find(*it) == M[i].end()) continue;
        dinic.add(0, i, M[i][*it], 0);
      } else {
        if (M[i].find(*it) == M[i].end()) continue;
        dinic.add(i, n + 1, M[i][*it], 0);
      }
    res += dinic.maxFlow();
  }
  cout << res << endl;
}
int main() {
  enter();
  solve();
  return 0;
}
