#include <bits/stdc++.h>
using namespace std;
class Ford_Fulkerson {
  vector<vector<pair<int, int> > > residual;
  vector<vector<pair<int, int> > > network;
  vector<int> path, vis;
  int get_path(int src, int sink, int min_cost = INT_MAX) {
    path.push_back(src);
    if (src == sink) {
      return min_cost;
    }
    int res = 0;
    vis[src] = 1;
    for (int x = 0; x < residual[src].size(); x++) {
      int j = residual[src][x].first;
      if (vis[j] || residual[src][x].second <= 0) continue;
      res = get_path(j, sink, min(min_cost, residual[src][x].second));
      if (res)
        break;
      else
        path.pop_back();
    }
    return res;
  }

 public:
  Ford_Fulkerson(vector<vector<pair<int, int> > > network) {
    this->network = network;
  }
  int get_max_flow(int src, int sink) {
    residual = network;
    int max_flow = 0, cur_flow;
    vis = vector<int>(residual.size(), 0);
    while ((cur_flow = get_path(src, sink))) {
      max_flow += cur_flow;
      for (int i = 0; i < path.size() - 1; i++) {
        int u = path[i];
        int v = path[i + 1];
        for (int k = 0; k < residual[u].size(); k++)
          if (residual[u][k].first == v) {
            residual[u][k].second -= cur_flow;
            break;
          }
        bool added = false;
        for (int k = 0; k < residual[v].size(); k++) {
          if (residual[v][k].first == u) {
            residual[v][k].second += cur_flow;
            added = true;
            break;
          }
        }
        if (!added) residual[v].push_back(make_pair(u, cur_flow));
      }
      vis = vector<int>(residual.size(), 0);
      path.clear();
    }
    return max_flow;
  }
};
vector<int> primeFactors(int n) {
  vector<int> res;
  while (n % 2 == 0) {
    res.push_back(2);
    n /= 2;
  }
  for (int i = 3; i * i <= n; i += 2) {
    while (n % i == 0) {
      res.push_back(i);
      n /= i;
    }
  }
  if (n > 2) res.push_back(n);
  return res;
}
int main() {
  int n, m, a[105], all = 0, cnt = 1;
  map<int, int> id[35];
  cin >> n >> m;
  vector<vector<int> > factors(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    factors[i] = primeFactors(a[i]);
    int mul = 1;
    for (int j = 0; j < factors[i].size(); j++) {
      id[j][i] = cnt++;
      mul *= factors[i][j];
    }
    assert(mul == a[i]);
    all += factors[i].size();
  }
  all += 2;
  vector<vector<pair<int, int> > > network(all);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    if (u & 1) swap(u, v);
    for (int j = 0; j < factors[u].size(); j++) {
      for (int k = 0; k < factors[v].size(); k++) {
        if (factors[u][j] == factors[v][k]) {
          assert(id[j].count(u) && id[k].count(v));
          network[id[j][u]].push_back(make_pair(id[k][v], 1));
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < factors[i].size(); j++) {
      assert(id[j].count(i));
      assert(id[j][i] > 0 && id[j][i] < all - 1);
      if (i % 2 == 0) {
        network[0].push_back(make_pair(id[j][i], 1));
      } else {
        network[id[j][i]].push_back(make_pair(all - 1, 1));
      }
    }
  }
  Ford_Fulkerson ford(network);
  cout << ford.get_max_flow(0, all - 1) << endl;
  return 0;
}
