#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int inf = 2e9;
int result[40008];
vector<int> v[40008];
int vis[40008];
int a[150];
int fin(int x) {
  if (vis[x]) return 0;
  vis[x] = 1;
  for (int i = 0; i < v[x].size(); i++) {
    int t = v[x][i];
    if (result[t] == 0 or fin(result[t]) == 1) {
      result[t] = x;
      return 1;
    }
  }
  return 0;
}
int n, m;
vector<int> primes;
vector<int> has[150];
vector<int> many[150];
int isit(int x) {
  if (x == 1) return 0;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) return 0;
  }
  return 1;
}
int usd[100080];
void ini() {
  for (int i = 2; i <= 100008; i++) {
    if (usd[i] == 0) {
      for (int j = i; j <= 100008; j += i) {
        usd[j] = 1;
      }
      primes.push_back(i);
    }
  }
}
int main() {
  ini();
  cin >> n >> m;
  for (int ii = 1; ii <= n; ii++) {
    cin >> a[ii];
    int t = a[ii];
    for (int i = 0; i < primes.size(); i++) {
      int num = 0;
      while (t % primes[i] == 0) {
        num++;
        t /= primes[i];
      }
      while (num--) has[ii].push_back(primes[i]);
    }
    if (isit(t)) {
      has[ii].push_back(t);
    }
  }
  while (m--) {
    int x, y;
    cin >> x >> y;
    if (x % 2 == 0) swap(x, y);
    for (int i = 0; i < has[x].size(); i++) {
      for (int j = 0; j < has[y].size(); j++) {
        int id1 = x * 36 + i, id2 = y * 36 + j;
        if (has[x][i] == has[y][j]) v[id1].push_back(id2);
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i += 2) {
    for (int j = 0; j < has[i].size(); j++) {
      int id = i * 36 + j;
      if (v[id].size() == 0) continue;
      memset(vis, 0, sizeof(vis));
      ans += fin(id);
    }
  }
  cout << ans;
}
