#include <bits/stdc++.h>
using namespace std;
const int64_t base = 31;
const int64_t oo = 1e3;
int64_t n, m, t = 0, visitedX[101][101];
pair<int64_t, int64_t> matchY[101][101];
vector<int64_t> edge[101], a[101];
void prepare() {
  cin >> n >> m;
  for (int64_t i = 1; i <= n; i++) {
    int64_t tmp;
    cin >> tmp;
    int64_t k = sqrt(tmp), j = 2;
    while (j <= k) {
      if (tmp % j)
        j++;
      else
        a[i].push_back(j), tmp /= j;
    }
    if (tmp != 1) a[i].push_back(tmp);
  }
  for (int64_t i = 1; i <= m; i++) {
    int64_t u, v;
    cin >> u >> v;
    if (v % 2) swap(u, v);
    edge[u].push_back(v);
  }
  for (int64_t i = 0; i <= n; i++)
    for (int64_t j = 0; j <= 100; j++)
      matchY[i][j].first = matchY[i][j].second = 0;
}
int64_t visit(int64_t x, int64_t y) {
  if (visitedX[x][y] == t) return 0;
  visitedX[x][y] = t;
  for (int64_t i : edge[x]) {
    for (int64_t j = 0; j < a[i].size(); j++) {
      if (a[x][y] != a[i][j]) continue;
      if (!matchY[i][j].first ||
          visit(matchY[i][j].first, matchY[i][j].second)) {
        matchY[i][j] = {x, y};
        return 1;
      }
    }
  }
  return 0;
}
void solve() {
  int64_t res = 0;
  for (int64_t i = 1; i <= n; i += 2) {
    for (int64_t j = 0; j < a[i].size(); j++) {
      t++;
      res += visit(i, j);
    }
  }
  cout << res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  prepare();
  solve();
  return 0;
}
