#include <bits/stdc++.h>
using namespace std;
int a[101];
int n, m;
vector<pair<int, int> > v[101];
int N;
int used[3000], mt[3000];
vector<int> g[3000];
int ans;
bool kuhn(int v) {
  if (used[v]) return 0;
  used[v] = 1;
  for (int i = 0; i < g[v].size(); i++) {
    int to = g[v][i];
    if (mt[to] == -1 || kuhn(mt[to])) {
      mt[to] = v;
      return 1;
    }
  }
  return 0;
}
vector<int> primeFactor(int x) {
  vector<int> ret;
  for (int j = 2; j <= x; j++) {
    while (x % j == 0) {
      ret.push_back(j);
      x = x / j;
    }
  }
  return ret;
}
int main() {
  scanf("%d %d", &n, &m);
  N = 0;
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    a[i] = x;
    for (int j = 2; j * j <= x; j++) {
      while (x % j == 0) {
        x = x / j;
        ++N;
        v[i].push_back(make_pair(j, N));
      }
    }
    if (x > 1) {
      N++;
      v[i].push_back(make_pair(x, N));
    }
  }
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d %d", &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 <= N; i++) mt[i] = -1;
  for (int i = 1; i <= N; i++) {
    memset(used, 0, sizeof used);
    kuhn(i);
  }
  for (int i = 1; i <= N; i++)
    if (mt[i] != -1) ans++;
  cout << ans / 2;
  return 0;
}
