#include <bits/stdc++.h>
using namespace std;
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
template <typename T>
ostream &operator<<(ostream &stream, vector<T> &v) {
  for (T &x : v) stream << x << " ";
  return stream;
}
template <typename T>
istream &operator>>(istream &stream, vector<T> &v) {
  for (T &x : v) stream >> x;
  return stream;
}
template <typename T>
T max(vector<T> &v) {
  return *(max_element(v.begin(), v.end()));
}
template <typename T>
T min(vector<T> &v) {
  return *(min_element(v.begin(), v.end()));
}
const long long inf = 1e18;
struct FlowEdge {
  long long v, u;
  long long cap, flow = 0;
  FlowEdge(long long v, long long u, long long cap) : v(v), u(u), cap(cap) {}
};
struct Dinic {
  const long long flow_inf = 1e18;
  vector<FlowEdge> edges;
  vector<vector<long long>> adj;
  long long n, m = 0;
  long long s, t;
  vector<long long> level, ptr;
  queue<long long> q;
  Dinic(long long n, long long s, long long t) : n(n), s(s), t(t) {
    adj.resize(n);
    level.resize(n);
    ptr.resize(n);
  }
  void add_edge(long long v, long long u, long long cap) {
    edges.emplace_back(v, u, cap);
    edges.emplace_back(u, v, 0);
    adj[v].push_back(m);
    adj[u].push_back(m + 1);
    m += 2;
  }
  bool bfs() {
    while (!q.empty()) {
      long long v = q.front();
      q.pop();
      for (long long id : adj[v]) {
        if (edges[id].cap - edges[id].flow < 1) continue;
        if (level[edges[id].u] != -1) continue;
        level[edges[id].u] = level[v] + 1;
        q.push(edges[id].u);
      }
    }
    return level[t] != -1;
  }
  long long dfs(long long v, long long pushed) {
    if (pushed == 0) return 0;
    if (v == t) return pushed;
    for (long long &cid = ptr[v]; cid < (long long)adj[v].size(); cid++) {
      long long id = adj[v][cid];
      long long u = edges[id].u;
      if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)
        continue;
      long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
      if (tr == 0) continue;
      edges[id].flow += tr;
      edges[id ^ 1].flow -= tr;
      return tr;
    }
    return 0;
  }
  long long flow() {
    long long f = 0;
    while (true) {
      fill(level.begin(), level.end(), -1);
      level[s] = 0;
      q.push(s);
      if (!bfs()) break;
      fill(ptr.begin(), ptr.end(), 0);
      while (long long pushed = dfs(s, flow_inf)) {
        f += pushed;
      }
    }
    return f;
  }
};
void solve() {
  long long n, m;
  cin >> n >> m;
  vector<long long> a(n + 1);
  for (long long i = 1; i <= n; i++) cin >> a[i];
  vector<pair<long long, long long>> b(m);
  for (long long i = 0; i < m; i++) {
    cin >> b[i].first >> b[i].second;
    if (b[i].first % 2) swap(b[i].first, b[i].second);
  }
  set<long long> primes;
  for (long long i = 1; i <= n; i++) {
    long long temp = a[i];
    for (long long j = 2; j * j <= temp; j++) {
      if (temp % j) continue;
      primes.insert(j);
      do {
        temp /= j;
      } while (temp % j == 0);
    }
    if (temp > 1) primes.insert(temp);
  }
  long long ans = 0;
  for (long long p : primes) {
    Dinic d(n + 2, 0, n + 1);
    for (auto [u, v] : b) d.add_edge(u, v, inf);
    for (long long i = 1; i <= n; i++) {
      if (a[i] % p) continue;
      long long cnt = 0;
      do {
        cnt++;
        a[i] /= p;
      } while (a[i] % p == 0);
      if (i % 2)
        d.add_edge(i, n + 1, cnt);
      else
        d.add_edge(0, i, cnt);
    }
    ans += d.flow();
  }
  cout << ans << "\n";
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
