#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
const int N = 10005;
template <class T>
bool read(T& x) {
  char c;
  while (!isdigit(c = getchar()) && c != '-' && c != EOF)
    ;
  if (c == EOF) return false;
  T flag = 1;
  if (c == '-') {
    flag = -1;
    x = 0;
  } else
    x = c - '0';
  while (isdigit(c = getchar())) x = x * 10 + c - '0';
  x *= flag;
  return true;
}
template <class T, class... R>
bool read(T& a, R&... b) {
  if (!read(a)) return false;
  return read(b...);
}
mt19937 gen(steady_clock::now().time_since_epoch().count());
vector<int> g[N];
int match[N], vis[N];
bool hungary_find(int u) {
  for (auto v : g[u]) {
    if (!vis[v]) {
      vis[v] = 1;
      if (match[v] == -1 || hungary_find(match[v])) {
        match[v] = u;
        return true;
      }
    }
  }
  return false;
}
int hungary(int n1, int n2) {
  for (int i = 0; i < n2; i++) match[i] = -1;
  int r = 0;
  for (int i = 0; i < n1; i++) {
    for (int i = 0; i < n2; i++) vis[i] = 0;
    if (hungary_find(i)) r++;
  }
  return r;
}
int a[N], s[N], t[N], b[2][N], nn[2];
void fact(int n, int res[], int s, int& t) {
  t = s;
  for (long long i = 2; i * i <= n;) {
    if (n % i == 0) {
      res[t++] = i;
      n /= i;
    } else
      i++;
  }
  if (n > 1) res[t++] = n;
}
int main() {
  time_point<steady_clock> start = steady_clock::now();
  int n, m, x, y;
  read(n, m);
  for (int i = 1; i <= n; i++) {
    read(a[i]);
    s[i] = nn[i & 1];
    fact(a[i], b[i & 1], s[i], t[i]);
    nn[i & 1] += t[i] - s[i];
  }
  while (m--) {
    read(x, y);
    for (int i = s[x]; i < t[x]; i++) {
      for (int j = s[y]; j < t[y]; j++) {
        if (b[x & 1][i] == b[y & 1][j]) {
          if (x & 1)
            g[j].push_back(i);
          else
            g[i].push_back(j);
        }
      }
    }
  }
  printf("%d\n", hungary(nn[0], nn[1]));
  cerr << endl
       << "------------------------------" << endl
       << "Time: "
       << duration<double, milli>(steady_clock::now() - start).count() << " ms."
       << endl;
  return 0;
}
