#include <bits/stdc++.h>
struct bipartiteMatching {
  int n;
  std::vector<std::vector<int>> e;
  std::vector<int> match;
  std::vector<bool> used;
  bipartiteMatching(int n) : n(n), e(n), match(n), used(n) {}
  void addEdge(int u, int v) {
    e[u].push_back(v);
    e[v].push_back(u);
  }
  bool dfs(int v) {
    used[v] = true;
    for (int u : e[v]) {
      int w = match[u];
      if (w < 0 || !used[w] && dfs(w)) {
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
    return false;
  }
  int count() {
    int ans = 0;
    bool flag = true;
    match.assign(n, -1);
    while (flag) {
      flag = false;
      used.assign(n, false);
      for (int v = 0; v < n; v++) {
        if (match[v] == -1 && dfs(v)) {
          ans++;
          flag = true;
        }
      }
    }
    return ans;
  }
};
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m;
  std::cin >> n >> m;
  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }
  int nd = 0;
  std::vector<std::vector<int>> d(n);
  std::vector<int> b(n);
  int sum = 0;
  for (int i = 0; i < n; i++) {
    b[i] = sum;
    int x = a[i];
    for (int j = 2; j * j <= x; j++) {
      if (x % j == 0) {
        int p = 1;
        while (x % j == 0) {
          p *= j;
          x /= j;
          d[i].push_back(j);
        }
      }
    }
    if (x > 1) {
      d[i].push_back(x);
    }
    sum += d[i].size();
  }
  bipartiteMatching g(sum);
  for (int i = 0; i < m; i++) {
    int u, v;
    std::cin >> u >> v;
    u--;
    v--;
    for (int i = 0; i < int(d[u].size()); i++) {
      for (int j = 0; j < int(d[v].size()); j++) {
        if (d[u][i] == d[v][j]) {
          g.addEdge(b[u] + i, b[v] + j);
        }
      }
    }
  }
  std::cout << g.count() << "\n";
  return 0;
}
