#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int inf = 1e9;
long long powm(long long a, long long p, long long m) {
  long long r = 1 % m;
  while (p) {
    if (p & 1) r = r * a % m;
    p >>= 1;
    a = a * a % m;
  }
  return r;
}
int used[3200], mt[3200];
vector<int> g[3200];
bool try_kuhn(int v) {
  if (used[v]) return false;
  used[v] = true;
  for (int i = 0; i < g[v].size(); ++i) {
    int to = g[v][i];
    if (mt[to] == -1 || try_kuhn(mt[to])) {
      mt[to] = v;
      return true;
    }
  }
  return false;
}
int main() {
  int n, m, a, ik, jk, ans = 0, ind[101] = {};
  scanf("%d%d", &n, &m);
  vector<int> var[100];
  for (int i = 0; i < (n); ++i) {
    scanf("%d", &a);
    for (int j = 2; j * j <= a; ++j) {
      int p = j;
      while (a % j == 0) {
        var[i].push_back(p);
        a /= j;
      }
    }
    if (a != 1) var[i].push_back(a);
  }
  for (int i = 0; i < (m); ++i) {
    scanf("%d%d", &ik, &jk);
    for (int x = 0; x < (((int)(var[ik - 1]).size())); ++x)
      for (int y = 0; y < (((int)(var[jk - 1]).size())); ++y)
        if (var[ik - 1][x] == var[jk - 1][y]) {
          g[32 * (ik - 1) + x].push_back(32 * (jk - 1) + y);
          g[32 * (jk - 1) + y].push_back(32 * (ik - 1) + x);
        }
  }
  memset(mt, -1, sizeof(mt));
  for (int v = 0; v < n; v += 2)
    for (int x = 0; x < (((int)(var[v]).size())); ++x) {
      memset(used, 0, sizeof(used));
      try_kuhn(32 * v + x);
    }
  for (int i = 0; i < n * 32; ++i) ans += mt[i] != -1;
  printf("%d\n", ans);
  return 0;
}
