#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[33 * 110 * 2];
vector<pair<int, int> > v[33 * 110 * 2];
vector<int> g[33 * 110 * 2];
int l, r;
int ans;
int used[33 * 110 * 2];
int mt[33 * 110 * 2];
bool try_kuhn(int v) {
  if (used[v]) return false;
  used[v] = true;
  for (size_t 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() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (i % 2 == 1) {
      for (int j = 2; j * j <= a[i]; j++) {
        while (a[i] % j == 0) {
          v[i].push_back(make_pair(j, ++l));
          a[i] /= j;
        }
      }
      if (a[i] != 1) {
        v[i].push_back(make_pair(a[i], ++l));
      }
    } else {
      for (int j = 2; j * j <= a[i]; j++) {
        while (a[i] % j == 0) {
          a[i] /= j;
          v[i].push_back(make_pair(j, ++r));
        }
      }
      if (a[i] != 1) {
        v[i].push_back(make_pair(a[i], ++r));
      }
    }
  }
  for (int k = 1; k <= m; k++) {
    int x, y;
    cin >> x >> y;
    if (x % 2 == 0) swap(x, y);
    for (int i = 0; i < v[x].size(); i++) {
      pair<int, int> xx = v[x][i], yy;
      for (int j = 0; j < v[y].size(); j++) {
        yy = v[y][j];
        if (xx.first == yy.first) {
          g[xx.second].push_back(yy.second);
        }
      }
    }
  }
  for (int i = 1; i <= r; i++) {
    mt[i] = -1;
  }
  for (int v = 1; v <= l; v++) {
    for (int i = 1; i <= l; i++) {
      used[i] = false;
    }
    try_kuhn(v);
  }
  for (int i = 1; i <= r; ++i) {
    if (mt[i] != -1) {
      ans++;
    }
  }
  cout << ans;
  return 0;
}
