#include <bits/stdc++.h>
using namespace std;
template <class T>
T min(T a, T b, T c) {
  return min(a, min(b, c));
}
template <class T>
T max(T a, T b, T c) {
  return max(a, max(b, c));
}
int a[105], p[105], q[105], s, t, n, m, ans;
int c[105][105], f[105][105], trace[105], delta[105];
map<int, bool> used[105];
bool FindPath() {
  queue<int> q;
  memset(trace, 0, sizeof trace);
  q.push(s);
  trace[s] = s;
  delta[s] = 1000000007;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v = (1); v <= (t); ++v) {
      if (trace[v] == 0) {
        if (c[u][v] - f[u][v] > 0) {
          trace[v] = u;
          delta[v] = min(delta[u], c[u][v] - f[u][v]);
          q.push(v);
          if (v == t) return true;
        } else if (f[v][u] > 0) {
          trace[v] = -u;
          delta[v] = min(delta[u], f[v][u]);
          q.push(v);
          if (v == t) return true;
        }
      }
    }
  }
  return false;
}
void IncFlow() {
  int v = t;
  while (v != s) {
    int u = trace[v];
    if (u < 0) {
      u = -u;
      f[v][u] -= delta[t];
    } else
      f[u][v] += delta[t];
    v = u;
  }
}
void Flow(int x) {
  s = 1;
  t = n + 2;
  int e[105];
  memset(e, 0, sizeof e);
  for (int i = (1); i <= (n); ++i) {
    while (a[i] % x == 0) {
      a[i] /= x;
      ++e[i];
    }
  }
  memset(c, 0, sizeof c);
  for (int i = (1); i <= (m); ++i) {
    c[p[i] + 1][q[i] + 1] = min(e[p[i]], e[q[i]]);
  }
  for (int i = (1); i <= ((n + 1) / 2); ++i) c[s][i * 2] = e[i * 2 - 1];
  for (int i = (1); i <= (n / 2); ++i) c[i * 2 + 1][t] = e[i * 2];
  memset(f, 0, sizeof f);
  while (FindPath()) {
    IncFlow();
  }
  for (int i = (1); i <= (m); ++i) {
    ans += f[p[i] + 1][q[i] + 1];
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (n); ++i) scanf("%d", &a[i]);
  for (int i = (1); i <= (m); ++i) {
    scanf("%d%d", &p[i], &q[i]);
    if (p[i] % 2 == 0) swap(p[i], q[i]);
  }
  for (int i = (1); i <= (n); ++i) {
    for (int j = (2); j <= ((int)sqrt(a[i])); ++j) {
      if (a[i] % j == 0) Flow(j);
    }
    if (a[i] > 1) Flow(a[i]);
  }
  cout << ans;
  return 0;
}
