#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1100, INF = 0x7FFFFFFF;
struct edge {
  int dest, rev, cap, f;
  edge(int dest, int rev, int cap) : dest(dest), rev(rev), cap(cap) { f = 0; }
};
int dist[MAXV + 1], ptr[MAXV + 1];
vector<edge> adj[MAXV + 1];
int V, S, T;
void add_edge(int a, int b, int cap) {
  adj[a].push_back(edge(b, adj[b].size(), cap));
  adj[b].push_back(edge(a, adj[a].size() - 1, 0));
}
bool bfs() {
  for (int i = 1; i <= V; i++) dist[i] = -1;
  dist[S] = 0;
  queue<int> q;
  q.push(S);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i = 0; i < adj[v].size(); i++) {
      edge e = adj[v][i];
      if (dist[e.dest] == -1 && e.cap > e.f) {
        dist[e.dest] = dist[v] + 1;
        q.push(e.dest);
      }
    }
  }
  return dist[T] != -1;
}
int dfs(int v, int f) {
  if (v == T) return f;
  for (; ptr[v] < adj[v].size(); ++ptr[v]) {
    edge &e = adj[v][ptr[v]];
    if (dist[e.dest] == dist[v] + 1 && e.cap > e.f) {
      int df = dfs(e.dest, min(f, e.cap - e.f));
      if (df > 0) {
        e.f += df;
        adj[e.dest][e.rev].f -= df;
        return df;
      }
    }
  }
  return 0;
}
int max_flow() {
  int flow = 0;
  while (bfs()) {
    for (int i = 1; i <= V; i++) ptr[i] = 0;
    while (true) {
      int df = dfs(S, INF);
      if (df == 0) break;
      flow += df;
    }
  }
  return flow;
}
void clear() {
  for (int i = 1; i <= V; i++) adj[i].clear();
}
vector<pair<int, int> > factorize(int n) {
  vector<pair<int, int> > v;
  for (int i = 2; i * i <= n; i++) {
    int count = 0;
    while ((n % i) == 0) {
      count++;
      n /= i;
    }
    if (count != 0) {
      v.push_back({i, count});
    }
  }
  if (n != 1) {
    v.push_back({n, 1});
  }
  return v;
}
const int MAX = 110;
vector<pair<int, int> > v[MAX];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  S = 1;
  V = T = 1100;
  clear();
  for (int i = 2; i <= n + 1; i++) {
    int aux;
    scanf("%d", &aux);
    v[i] = factorize(aux);
    if (i % 2) {
      for (int j = 0; j < v[i].size(); j++) {
        add_edge(S, i + n * j, v[i][j].second);
      }
    } else {
      for (int j = 0; j < v[i].size(); j++) {
        add_edge(i + n * j, T, v[i][j].second);
      }
    }
  }
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a++;
    b++;
    if (b % 2) swap(a, b);
    if (a % 2) {
      for (int j = 0; j < v[a].size(); j++) {
        for (int k = 0; k < v[b].size(); k++) {
          if (v[a][j].first == v[b][k].first) {
            add_edge(a + n * j, b + n * k, min(v[a][j].second, v[b][k].second));
          }
        }
      }
    }
  }
  printf("%d\n", max_flow());
}
