#include <bits/stdc++.h>
using namespace std;
const int N = 123456;
int a[N];
int x[N];
int y[N];
map<int, int> cnt[N];
vector<int> g[N];
int primes[N];
int p[N];
int was[N];
int from[N];
int to[N];
int st;
int go(int x) {
  if (x == -1) {
    return 1;
  }
  if (was[x] == st) {
    return 0;
  }
  was[x] = st;
  int sz = g[x].size();
  for (int i = 0; i < sz; ++i) {
    int y = g[x][i];
    if (go(p[y])) {
      p[y] = x;
      return 1;
    }
  }
  return 0;
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
  }
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", x + i, y + i);
    --x[i];
    --y[i];
  }
  int size = 0;
  for (int i = 0; i < n; ++i) {
    cnt[i].clear();
    int x = a[i];
    for (int j = 2; j * j <= x; ++j) {
      if (x % j == 0) {
        while (x % j == 0) {
          x /= j;
          cnt[i][j] += 1;
        }
        primes[size++] = j;
      }
    }
    if (x > 1) {
      cnt[i][x] += 1;
      primes[size++] = x;
    }
  }
  sort(primes, primes + size);
  size = unique(primes, primes + size) - primes;
  memset(was, 0, sizeof was);
  st = 1;
  int ans = 0;
  for (int i = 0; i < size; ++i) {
    from[0] = 0;
    to[0] = cnt[0][primes[i]];
    for (int j = 1; j < n; ++j) {
      from[j] = to[j - 1];
      to[j] = from[j] + cnt[j][primes[i]];
    }
    for (int j = 0; j < to[n - 1]; ++j) {
      g[j].clear();
    }
    for (int j = 0; j < m; ++j) {
      int aa = x[j] % 2 == 0 ? x[j] : y[j];
      int bb = y[j] % 2 == 1 ? y[j] : x[j];
      for (int xx = from[aa]; xx < to[aa]; ++xx) {
        for (int yy = from[bb]; yy < to[bb]; ++yy) {
          g[xx].push_back(yy);
        }
      }
    }
    for (int j = 0; j < to[n - 1]; ++j) {
      p[j] = -1;
    }
    for (int j = 0; j < to[n - 1]; ++j) {
      ans += go(j);
      ++st;
    }
  }
  printf("%d\n", ans);
  return 0;
}
