#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100 + 1;
const int LOG_N = 30;
const int MAX_M = LOG_N * MAX_N;
int n, m;
int a[MAX_N];
int no;
int O[MAX_M];
int P[MAX_M];
int f[MAX_N][MAX_N];
vector<int> E[MAX_M];
int match[MAX_M];
int vis[MAX_M];
int augment(int u) {
  if (vis[u]++) return 0;
  for (int v : E[u]) {
    if (match[v] == -1 || augment(match[v])) {
      match[v] = u;
      return 1;
    }
  }
  return 0;
}
int main() {
  int u, v;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    int x = a[i];
    for (int j = 2; j * j <= x; j++) {
      while (x % j == 0) {
        O[no] = i, P[no] = j;
        no++;
        x /= j;
      }
    }
    if (x != 1) O[no] = i, P[no] = x, no++;
  }
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    f[u - 1][v - 1] = f[v - 1][u - 1] = 1;
  }
  for (int i = 0; i < no; i++)
    for (int j = 0; j < no; j++)
      if (P[i] == P[j] && f[O[i]][O[j]]) E[i].push_back(j);
  memset(match, -1, sizeof match);
  int mcbm = 0;
  for (int i = 0; i < no; i++) {
    if (O[i] % 2 == 0) {
      memset(vis, 0, sizeof vis);
      mcbm += augment(i);
    }
  }
  printf("%d\n", mcbm);
  return 0;
}
