#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 10;
const long long M = 1e12;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const long long inf = -1e18;
long long n, m, num[N], us[N], x, y, k, ans;
vector<pair<long long, long long> > gr[N];
vector<long long> g[N];
bool dfs(long long x) {
  for (auto i : g[x]) {
    if (us[i]) continue;
    us[i] = 1;
    if (num[i] == 0 || dfs(num[i])) {
      num[i] = x;
      return 1;
    }
  }
  return 0;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    for (int j = 2; j * j <= x; j++) {
      while (x % j == 0) {
        k++;
        gr[i].push_back({j, k});
        x /= j;
      }
    }
    if (x > 1) {
      k++;
      gr[i].push_back({x, k});
    }
  }
  for (int i = 1; i <= m; i++) {
    cin >> x >> y;
    if (x % 2 == 0) swap(x, y);
    for (auto x1 : gr[x]) {
      for (auto y1 : gr[y]) {
        if (x1.first == y1.first) {
          g[x1.second].push_back(y1.second);
        }
      }
    }
  }
  for (int i = 1; i <= k; i++) {
    memset(us, 0, sizeof us);
    ans += dfs(i);
  }
  cout << ans;
  return 0;
}
