#include <bits/stdc++.h>
using namespace std;
const int MAX_FL_N = 110;
const int FL_INF = 1e9;
struct edge;
vector<edge> ve[MAX_FL_N];
struct edge {
  int v, fl, r;
  edge(int _v = 0, int _fl = 0, int _r = 0) : v(_v), fl(_fl), r(_r) {}
  void add(int a) {
    fl += a;
    ve[v][r].fl -= a;
  }
  int cap() { return ve[v][r].fl; }
};
void add_edge(int v, int w, int c) {
  ve[v].push_back(edge(w, 0, ((int)((ve[w]).size())) + (v == w ? 1 : 0)));
  ve[w].push_back(edge(v, c, ((int)((ve[v]).size())) - 1));
}
int dist[MAX_FL_N], cur[MAX_FL_N], S, T, N;
int bfs() {
  int v;
  memset(dist, -1, sizeof(int) * (N + 1));
  queue<int> Q;
  dist[S] = 0;
  Q.push(S);
  while (!Q.empty()) {
    v = Q.front();
    Q.pop();
    for (__typeof((ve[v]).begin()) it = (ve[v]).begin(); it != (ve[v]).end();
         ++it) {
      if (it->cap() > 0 && dist[it->v] == -1) {
        dist[it->v] = dist[v] + 1;
        Q.push(it->v);
      }
    }
  }
  return dist[T] != -1;
}
int dfs(int v, int mn) {
  if (v == T || mn == 0) return mn;
  int &i = cur[v], k, y, res = 0;
  for (; i < ((int)((ve[v]).size())); ++i) {
    k = ve[v][i].v;
    if (dist[k] == dist[v] + 1 && ve[v][i].cap() > 0) {
      y = dfs(k, min(mn, ve[v][i].cap()));
      mn -= y;
      res += y;
      ve[v][i].add(y);
      if (mn == 0) break;
    }
  }
  return res;
}
int flow() {
  int res = 0;
  while (bfs()) {
    memset(cur, 0, sizeof(int) * (N + 1));
    res += dfs(S, FL_INF);
  }
  return res;
}
int main(void) {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> a(n);
  for (int i = 0; i < (n); ++i) {
    scanf("%d", &a[i]);
  }
  vector<pair<int, int> > E(m);
  for (int i = 0; i < (m); ++i) {
    scanf("%d%d", &E[i].first, &E[i].second);
    --E[i].first;
    --E[i].second;
    if (E[i].first % 2 == 1) {
      swap(E[i].first, E[i].second);
    }
  }
  set<int> P;
  for (int i = 0; i < (n); ++i) {
    int g = a[i];
    for (int p = 2; p * p <= a[i]; ++p) {
      int k = 0;
      while (g % p == 0) {
        g /= p;
        ++k;
      }
      if (k > 0) {
        P.insert(p);
      }
    }
    if (g > 1) {
      P.insert(g);
    }
  }
  int res = 0;
  N = n + 2;
  S = N - 1;
  T = N - 2;
  for (int p : P) {
    for (int i = 0; i < (N); ++i) {
      ve[i].clear();
    }
    for (int i = 0; i < (n); ++i) {
      int k = 0;
      while (a[i] % p == 0) {
        a[i] /= p;
        ++k;
      }
      if (i % 2 == 0) {
        add_edge(S, i, k);
      } else {
        add_edge(i, T, k);
      }
    }
    for (const pair<int, int> &e : E) {
      add_edge(e.first, e.second, 1000);
    }
    res += flow();
  }
  printf("%d\n", res);
  return 0;
}
