#include <bits/stdc++.h>
using namespace std;
const int maxn = 3100;
struct xx {
  int x, y;
} pa[101];
int n, m;
int primenum;
int num1, num2;
int a[101];
bool f[100010];
int prime[100010];
int v[maxn], val[maxn];
int setx[maxn], sety[maxn];
vector<int> se[122];
vector<int> g[maxn];
void get_prime() {
  memset(f, 0, sizeof(f));
  primenum = 0;
  for (int i = 2; i <= 100000; i++) {
    if (f[i] == 0) {
      prime[++primenum] = i;
      int j = i + i;
      while (j <= 100000) {
        f[j] = 1;
        j += i;
      }
    }
  }
}
void build() {
  num1 = num2 = 0;
  for (int i = 1; i <= n; i++) se[i].clear();
  for (int i = 1; i <= n; i += 2) {
    for (int j = 1; j <= primenum; j++) {
      if (prime[j] > a[i]) break;
      while (a[i] % prime[j] == 0) {
        a[i] /= prime[j];
        val[++num1] = prime[j];
        se[i].push_back(num1);
      }
    }
    if (a[i] > 1) {
      val[++num1] = a[i];
      se[i].push_back(num1);
    }
  }
  for (int i = 2; i <= n; i += 2) {
    for (int j = 1; j <= primenum; j++) {
      if (prime[j] > a[i]) break;
      while (a[i] % prime[j] == 0) {
        a[i] /= prime[j];
        num2++;
        val[num1 + num2] = prime[j];
        se[i].push_back(num1 + num2);
      }
    }
    if (a[i] > 1) {
      num2++;
      val[num1 + num2] = a[i];
      se[i].push_back(num1 + num2);
    }
  }
  for (int i = 1; i <= num1 + num2; i++) g[i].clear();
  for (int i = 1; i <= m; i++) {
    int x = pa[i].x;
    int y = pa[i].y;
    for (int j = 0; j < se[x].size(); j++) {
      for (int k = 0; k < se[y].size(); k++) {
        int p1 = se[x][j];
        int p2 = se[y][k];
        if (val[p1] == val[p2]) {
          if (x & 1)
            g[p1].push_back(p2);
          else
            g[p2].push_back(p1);
        }
      }
    }
  }
}
void init() {
  get_prime();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) scanf("%d%d", &pa[i].x, &pa[i].y);
}
bool dfs(int root) {
  for (int j = 0; j < g[root].size(); j++) {
    int i = g[root][j];
    if (!v[i]) {
      v[i] = 1;
      if (sety[i] == -1 || dfs(sety[i])) {
        setx[root] = i;
        sety[i] = root;
        return true;
      }
    }
  }
  return false;
}
int main() {
  init();
  build();
  int ans = 0;
  memset(setx, -1, sizeof(setx));
  memset(sety, -1, sizeof(sety));
  for (int i = 1; i <= num1; i++) {
    if (setx[i] == -1) {
      memset(v, 0, sizeof(v));
      if (dfs(i)) ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}
