#include <bits/stdc++.h>
using namespace std;
void fast() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
struct Flow {
  const int INF = 1e9 + 9;
  int n, source, sink, idx = 0;
  vector<vector<int>> v, capacity;
  vector<vector<int>> paths;
  Flow(int n, int s, int t) {
    this->n = n;
    this->source = s;
    this->sink = t;
    v.resize(n + 1);
    capacity.resize(n + 1, vector<int>(n + 1, 0));
  }
  void add_edge(int a, int b, int cap) {
    capacity[a][b] = cap;
    capacity[b][a] = 0;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  int bfs(vector<int> &par) {
    fill(par.begin(), par.end(), -1);
    queue<pair<int, int>> q;
    par[source] = -2;
    q.push(make_pair(source, INF));
    while (!q.empty()) {
      auto t = q.front();
      q.pop();
      for (int i : v[t.first]) {
        if (par[i] == -1 && capacity[t.first][i] > 0) {
          par[i] = t.first;
          int new_flow = min(t.second, capacity[t.first][i]);
          if (i == sink) return new_flow;
          q.push(make_pair(i, new_flow));
        }
      }
    }
    return 0;
  }
  int getFlow() {
    int flow = 0;
    vector<int> par(n + 1, -1);
    while (1) {
      int new_flow = bfs(par);
      if (new_flow == 0) break;
      flow += new_flow;
      vector<int> augmentedPath;
      augmentedPath.push_back(sink);
      int temp = sink;
      while (temp != source) {
        int p = par[temp];
        augmentedPath.push_back(p);
        capacity[p][temp] -= new_flow;
        capacity[temp][p] += new_flow;
        temp = p;
      }
      reverse(augmentedPath.begin(), augmentedPath.end());
      paths.push_back(augmentedPath);
    }
    return flow;
  }
};
const int INF = 1e9 + 9;
const int N = 200;
vector<int> v(N);
vector<pair<int, int>> edges;
int n, m;
int getans(int x) {
  Flow flow(n + 1, 0, n + 1);
  for (int i = 1; i <= n; i++) {
    int c = 0, temp = v[i];
    while (temp % x == 0) {
      temp /= x;
      c++;
    }
    if (i & 1)
      flow.add_edge(0, i, c);
    else
      flow.add_edge(i, n + 1, c);
  }
  for (auto &i : edges) {
    if (i.first & 1)
      flow.add_edge(i.first, i.second, INF);
    else
      flow.add_edge(i.second, i.first, INF);
  }
  return flow.getFlow();
}
void solve() {
  set<int> s;
  for (int i = 1; i <= n; i++) {
    int temp = v[i];
    for (int j = 2; j * j <= v[i]; j++) {
      if (temp % j != 0) continue;
      s.insert(j);
      while (temp % j == 0) temp /= j;
    }
    if (temp > 1) s.insert(temp);
  }
  int ans = 0;
  for (int i : s) {
    ans += getans(i);
  }
  cout << ans << "\n";
}
int main() {
  fast();
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> v[i];
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    edges.push_back(make_pair(a, b));
  }
  solve();
}
