#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> G[11111];
vector<int> g[11111];
set<int> nodes;
int match[11111], node;
int seen[11111];
inline bool bpm(int i) {
  for (auto x : g[i]) {
    if (!seen[x]) {
      seen[x] = 1;
      if (match[x] == -1 or bpm(match[x])) {
        match[x] = i;
        return true;
      }
    }
  }
  return false;
}
int main() {
  node = 0;
  int n, m;
  scanf("%d", &n);
  ;
  scanf("%d", &m);
  ;
  for (int x = 1; x <= n; x++) {
    int a;
    scanf("%d", &a);
    ;
    for (int y = 2; y <= sqrt(a); y++) {
      while (a % y == 0) {
        G[x].emplace_back(y, ++node);
        a /= y;
      }
    }
    if (a > 1) G[x].emplace_back(a, ++node);
  }
  memset(match, -1, sizeof(match));
  ;
  memset(seen, 0, sizeof(seen));
  ;
  int res = 0;
  while (m--) {
    int l, r;
    scanf("%d", &l);
    ;
    scanf("%d", &r);
    ;
    if (l & 1) swap(l, r);
    for (auto y : G[l]) {
      for (auto z : G[r])
        if (y.first == z.first) {
          g[y.second].emplace_back(z.second);
          nodes.insert(y.second);
        }
    }
  }
  for (auto x : nodes) {
    memset(seen, 0, sizeof(seen));
    ;
    res += bpm(x);
  }
  printf("%d\n", res);
}
