#include <bits/stdc++.h>
using namespace std;
int a[200];
vector<pair<int, int> > v[200];
vector<int> g[100500];
bool used[100500];
int p[100500];
int cur = 0;
int n, m, ans = 0;
bool dfs(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 (p[to] == -1 || dfs(p[to])) {
      p[to] = v;
      return true;
    }
  }
  return false;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    int x = a[i];
    for (int j = 2; j * j <= x; j++)
      while (x % j == 0) {
        x /= j;
        v[i].push_back(make_pair(j, ++cur));
      }
    if (x > 1) v[i].push_back(make_pair(x, ++cur));
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    for (int j = 0; j < v[x].size(); j++)
      for (int k = 0; k < v[y].size(); k++)
        if (v[x][j].first == v[y][k].first) {
          g[v[x][j].second].push_back(v[y][k].second);
          g[v[y][k].second].push_back(v[x][j].second);
        }
  }
  for (int i = 1; i <= cur; i++) p[i] = -1;
  for (int i = 1; i <= cur; i++) {
    memset(used, 0, sizeof used);
    dfs(i);
  }
  for (int i = 1; i <= cur; i++)
    if (p[i] != -1) ans++;
  cout << ans / 2;
  return 0;
}
