#include <bits/stdc++.h>
using namespace std;
int match[2005];
int visited[2005];
vector<int> adj[2005];
vector<pair<int, int>> factors[105];
int cookie;
int dfs(int x) {
  if (visited[x] == cookie) return 0;
  visited[x] = cookie;
  for (int y : adj[x]) {
    if (match[y] == -1 || dfs(match[y])) {
      match[y] = x;
      return 1;
    }
  }
  return 0;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, m;
  cin >> n >> m;
  int size[2] = {};
  for (int i = 1; i <= n; ++i) {
    int num;
    cin >> num;
    for (int j = 2; j * j <= num; ++j) {
      while (num % j == 0) {
        factors[i].push_back({j, size[i % 2]++});
        num /= j;
      }
    }
    if (num > 1) {
      factors[i].push_back({num, size[i % 2]++});
    }
  }
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    if (l % 2) swap(l, r);
    for (auto [p1, i1] : factors[l]) {
      for (auto [p2, i2] : factors[r]) {
        if (p1 == p2) {
          adj[i1].push_back(i2);
        }
      }
    }
  }
  int sol = 0;
  memset(match, -1, sizeof match);
  for (int i = 0; i < size[0]; ++i) {
    cookie++;
    sol += dfs(i);
  }
  cout << sol << '\n';
}
