#include <bits/stdc++.h>
using namespace std;
vector<int> primes;
bitset<100000> prime;
void sieve() {
  primes.clear();
  prime.set();
  primes.push_back(2);
  for (int i = 4; i < 100000; i += 2) prime[i] = false;
  for (int i = 3; i < 100000; i += 2) {
    if (prime[i]) {
      primes.push_back(i);
      for (long long j = (long long)i * i; j < 100000; j += i) prime[j] = false;
    }
  }
}
vector<int> nums;
vector<int> vertices;
vector<bool> visited;
vector<int> match;
vector<int> lo, hi;
vector<vector<int>> adj_list;
int n, m;
int try_match(int u) {
  if (visited[u]) return 0;
  visited[u] = true;
  for (int v : adj_list[u]) {
    if (match[v] < 0 || try_match(match[v])) {
      match[v] = u;
      return 1;
    }
  }
  return 0;
}
void create_adjs(int u, int v) {
  for (int i = lo[u]; i <= hi[u]; i++) {
    for (int j = lo[v]; j <= hi[v]; j++) {
      if (vertices[i] < vertices[j])
        break;
      else if (vertices[i] == vertices[j])
        adj_list[i].push_back(j);
    }
  }
}
void create_vertices_lo(int id) {
  int val = nums[id];
  for (int p : primes) {
    if (val == 1) break;
    while (val % p == 0) {
      vertices.push_back(p);
      val /= p;
    }
  }
  if (val > 1) {
    vertices.push_back(val);
  }
  if (id == 0) {
    lo[id] = 0;
  } else {
    lo[id] = hi[id - 1] + 1;
  }
  hi[id] = vertices.size() - 1;
}
int main() {
  sieve();
  cin >> n >> m;
  nums.assign(n, 0);
  lo.assign(n, 0);
  hi.assign(n, 0);
  for (int i = 0; i < n; i++) {
    cin >> nums[i];
  }
  for (int i = 0; i < n; i++) {
    create_vertices_lo(i);
  }
  adj_list.assign(vertices.size(), vector<int>());
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if (a % 2) swap(a, b);
    create_adjs(a, b);
  }
  int nvert = vertices.size();
  match.assign(nvert, -1);
  int mcbm = 0;
  for (int i = 0; i < nvert; i++) {
    visited.assign(nvert, false);
    mcbm += try_match(i);
  }
  cout << mcbm << endl;
  return 0;
}
