#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct EdmondsKarp {
  int size;
  vector<vector<int> > adj, cap;
  vector<bool> vis;
  vector<int> p;
  EdmondsKarp(int _size) {
    size = _size;
    adj.assign(size, vector<int>());
    cap.assign(size, vector<int>());
    for (int i = 0; i < size; i++) cap[i].assign(size, 0);
  }
  void add_edge(int u, int v, int c) {
    adj[u].push_back(v);
    adj[v].push_back(u);
    cap[u][v] += c;
  }
  int augment(int v, int mini) {
    int u = p[v];
    if (u == -1) return mini;
    int f = augment(u, min(mini, cap[u][v]));
    cap[u][v] -= f;
    cap[v][u] += f;
    return f;
  }
  int flow(int s, int t) {
    int max_flow = 0;
    while (1) {
      queue<int> q;
      q.push(s);
      vis.assign(size, 0);
      vis[s] = 1;
      p.assign(size, -1);
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto v : adj[u]) {
          if (cap[u][v] > 0 && !vis[v]) {
            vis[v] = 1;
            p[v] = u;
            q.push(v);
          }
        }
      }
      if (!vis[t]) break;
      int f = augment(t, INF);
      if (f == 0) break;
      max_flow += f;
    }
    return max_flow;
  }
};
vector<int> prime;
vector<bool> is_prime;
void sieve() {
  int size = sqrt(1e9);
  int sqrt_size = sqrt(size);
  is_prime.assign(size + 1, 1);
  is_prime[0] = is_prime[1] = 0;
  for (int i = 2; i <= sqrt_size; i++) {
    if (!is_prime[i]) continue;
    for (int j = i * i; j <= size; j += i) is_prime[j] = 0;
  }
  for (int i = 2; i <= size; i++) {
    if (is_prime[i]) prime.push_back(i);
  }
}
int n, m, a[100];
vector<int> prime_factor[100];
map<pair<int, int>, pair<int, int> > change;
int main() {
  sieve();
  scanf("%d %d", &n, &m);
  int size = 1;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    for (auto j : prime) {
      int k = 0;
      while (a[i] % j == 0) {
        a[i] /= j;
        k++;
      }
      if (k) {
        change[{i, j}] = {size++, k};
        prime_factor[i].push_back(j);
      }
    }
    if (a[i] != 1) {
      change[{i, a[i]}] = {size++, 1};
      prime_factor[i].push_back(a[i]);
    }
  }
  size++;
  EdmondsKarp mf(size);
  for (int i = 0; i < n; i++) {
    for (auto j : prime_factor[i]) {
      pair<int, int> x = change[{i, j}];
      if (i % 2 == 0)
        mf.add_edge(0, x.first, x.second);
      else
        mf.add_edge(x.first, size - 1, x.second);
    }
  }
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    u--;
    v--;
    if (u % 2 != 0) swap(u, v);
    for (auto j : prime_factor[u]) {
      for (auto k : prime_factor[v]) {
        if (j == k) {
          pair<int, int> x = change[{u, j}];
          pair<int, int> y = change[{v, k}];
          mf.add_edge(x.first, y.first, INF);
        }
      }
    }
  }
  printf("%d\n", mf.flow(0, size - 1));
  return 0;
}
