#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);
mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());
const int N = 105;
pair<long long, long long> e[N];
long long n, m, a[N];
vector<vector<int>> capacity;
vector<vector<int>> adj;
int bfs(int s, int t, vector<int>& parent) {
  fill(parent.begin(), parent.end(), -1);
  parent[s] = -2;
  queue<pair<int, int>> q;
  q.push({s, MOD});
  while (!q.empty()) {
    int cur = q.front().first;
    int flow = q.front().second;
    q.pop();
    for (int next : adj[cur]) {
      if (parent[next] == -1 && capacity[cur][next]) {
        parent[next] = cur;
        int new_flow = min(flow, capacity[cur][next]);
        if (next == t) return new_flow;
        q.push({next, new_flow});
      }
    }
  }
  return 0;
}
int maxflow(int s, int t) {
  int flow = 0;
  vector<int> parent(N);
  int new_flow;
  while (new_flow = bfs(s, t, parent)) {
    flow += new_flow;
    int cur = t;
    while (cur != s) {
      int prev = parent[cur];
      capacity[prev][cur] -= new_flow;
      capacity[cur][prev] += new_flow;
      cur = prev;
    }
  }
  return flow;
}
void add_primes(long long x, set<long long>& primes) {
  for (int i = 2; i <= x / i; ++i) {
    if (x % i == 0) {
      primes.insert(i);
      while (x % i == 0) x /= i;
    }
  }
  if (x != 1) primes.insert(x);
}
long long cnt(long long x, long long p) {
  long long ret = 0;
  while (x && x % p == 0) {
    ++ret;
    x /= p;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  cin >> n >> m;
  adj = vector<vector<int>>(N);
  capacity = vector<vector<int>>(N, vector<int>(N));
  set<long long> primes;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    add_primes(a[i], primes);
  }
  for (int i = 1; i <= n; ++i) {
    if (i & 1) {
      adj[0].push_back(i);
      adj[i].push_back(0);
    } else {
      adj[n + 1].push_back(i);
      adj[i].push_back(n + 1);
    }
  }
  for (int i = 0; i < m; ++i) {
    cin >> e[i].first >> e[i].second;
    int u = e[i].first;
    int v = e[i].second;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  long long ans = 0;
  for (auto p : primes) {
    for (int i = 1; i <= n; ++i) {
      if (i & 1)
        capacity[0][i] = cnt(a[i], p);
      else
        capacity[i][n + 1] = cnt(a[i], p);
    }
    for (int i = 0; i < m; ++i) {
      int u = e[i].first;
      int v = e[i].second;
      if (u & 1)
        capacity[u][v] = cnt(a[u], p);
      else
        capacity[v][u] = cnt(a[v], p);
    }
    ans += maxflow(0, n + 1);
  }
  cout << ans << "\n";
}
