#include <bits/stdc++.h>
constexpr int MAX = 2 * 100 + 5;
constexpr int INF = 1e9;
using namespace std;
int edges[MAX][MAX];
int pedges[MAX][MAX];
int source = MAX - 2;
int sink = MAX - 1;
map<int, int> factors[MAX];
set<int> primes;
int n, m;
vector<int> bfs() {
  int parent[MAX];
  deque<int> todo{source};
  for (int i = 0; i < MAX; i++) {
    parent[i] = -1;
  }
  parent[source] = source;
  while (!todo.empty()) {
    int p = todo.front();
    for (int i = 0; i < MAX; i++) {
      if (pedges[p][i] != 0 && parent[i] == -1) {
        parent[i] = p;
        todo.push_back(i);
      }
    }
    todo.pop_front();
  }
  vector<int> ret;
  if (parent[sink] == -1)
    return ret;
  else
    ret.push_back(sink);
  while (ret.back() != source) {
    ret.push_back(parent[ret.back()]);
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
int max_flow() {
  vector<int> path = bfs();
  int ret = 0;
  while (!path.empty()) {
    for (auto v : path) {
    }
    int k = INF;
    for (int i = 0; i < path.size() - 1; i++) {
      k = min(pedges[path[i]][path[i + 1]], k);
    }
    ret += k;
    for (int i = 0; i < path.size() - 1; i++) {
      pedges[path[i]][path[i + 1]] -= k;
      pedges[path[i + 1]][path[i]] += k;
    }
    path = bfs();
  }
  return ret;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    for (int j = 2; j <= sqrt(1e9); j++) {
      if (a % j != 0) continue;
      factors[i][j] = 0;
      primes.emplace(j);
      while (a % j == 0) {
        factors[i][j]++;
        a /= j;
      }
    }
    if (a != 1) {
      factors[i][a] = 1;
      primes.emplace(a);
    }
  }
  for (int i = 0; i < m; i++) {
    int e1, e2;
    cin >> e1 >> e2;
    if (e1 % 2 == 1) {
      edges[2 * e1 + 1][2 * e2] = 1;
    } else {
      edges[2 * e2 + 1][2 * e1] = 1;
    }
  }
  int ret = 0;
  for (int p : primes) {
    for (int i = 0; i < MAX; i++) {
      for (int j = 0; j < MAX; j++) {
        pedges[i][j] = 0;
      }
    }
    for (int i = 1; i <= n; i++) {
      pedges[2 * i][2 * i + 1] = factors[i].count(p) == 0 ? 0 : factors[i][p];
    }
    for (int i = 1; i <= n; i += 2) {
      for (int j = 2; j <= n; j += 2) {
        pedges[2 * i + 1][2 * j] = edges[2 * i + 1][2 * j] * INF;
      }
    }
    for (int i = 1; i <= n; i++) {
      if (i % 2 == 0) {
        pedges[2 * i + 1][sink] = INF;
      } else {
        pedges[source][2 * i] = INF;
      }
    }
    ret += max_flow();
  }
  cout << ret << endl;
}
