#include <bits/stdc++.h>
using namespace std;
const int N = 300009;
const int mod = 1000000007;
template <class T>
T edmondsKarp(vector<unordered_map<int, T>>& graph, int source, int sink) {
  assert(source != sink);
  T flow = 0;
  vector<int> par((int)((graph).size())), q = par;
  for (;;) {
    fill(par.begin(), par.end(), -1);
    par[source] = 0;
    int ptr = 1;
    q[0] = source;
    for (int i = 0; i < (ptr); ++i) {
      int x = q[i];
      for (auto e : graph[x]) {
        if (par[e.first] == -1 && e.second > 0) {
          par[e.first] = x;
          q[ptr++] = e.first;
          if (e.first == sink) goto out;
        }
      }
    }
    return flow;
  out:
    T inc = numeric_limits<T>::max();
    for (int y = sink; y != source; y = par[y])
      inc = min(inc, graph[par[y]][y]);
    flow += inc;
    for (int y = sink; y != source; y = par[y]) {
      int p = par[y];
      if ((graph[p][y] -= inc) <= 0) graph[p].erase(y);
      graph[y][p] += inc;
    }
  }
}
void pre() {}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin.exceptions(cin.failbit);
  ;
  pre();
  int n, m;
  cin >> n >> m;
  set<int> s;
  vector<int> a(n);
  for (auto& it : a) cin >> it;
  vector<vector<int>> v(n + 1);
  int x, y;
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  int second = 0;
  int T = n + 1;
  int tmp;
  for (int j = 0; j < (n); ++j) {
    tmp = a[j];
    for (int i = 2; (i * i) <= a[j]; i++) {
      if ((a[j] % i) == 0) {
        s.insert(i);
        while (a[j] % i == 0) a[j] /= i;
      }
    }
    if (a[j] > 1) {
      s.insert(a[j]);
    }
    a[j] = tmp;
  }
  int ans = 0, temp, res;
  vector<unordered_map<int, int>> graph(n + 2);
  for (auto& it : s) {
    graph.clear();
    graph.resize(n + 2);
    for (int i = 0; i < n; i++) {
      res = 0;
      temp = a[i];
      while (temp % it == 0) {
        temp /= it;
        res++;
      }
      if (i % 2 == 0)
        graph[0][i + 1] = res;
      else
        graph[i + 1][n + 1] = res;
      for (auto& it : v[i + 1]) {
        if (it % 2 == 0) {
          graph[i + 1][it] = 100;
        }
      }
    }
    ans += edmondsKarp<int>(graph, second, T);
  }
  cout << ans << "\n";
  return 0;
}
