#include <bits/stdc++.h>
using namespace std;
const long long N = 2003;
const long long inf = 1e13;
struct Matching {
  long long n;
  vector<long long> matchL, matchR, dist;
  vector<vector<long long> > g;
  Matching(long long n)
      : n(n), matchL(n + 1), matchR(n + 1), dist(n + 1), g(n + 1) {}
  void addEdge(long long u, long long v) { g[u].push_back(v); }
  long long bfs() {
    queue<long long> q;
    for (long long i = 1; i <= n; i++) {
      if (!matchL[i]) {
        dist[i] = 0;
        q.push(i);
      } else
        dist[i] = inf;
    }
    dist[0] = inf;
    while (!q.empty()) {
      long long u = q.front();
      q.pop();
      for (auto it : g[u]) {
        if (dist[matchR[it]] == inf) {
          dist[matchR[it]] = dist[u] + 1;
          q.push(matchR[it]);
        }
      }
    }
    return (dist[0] != inf);
  }
  long long dfs(long long u) {
    if (u) {
      for (auto it : g[u]) {
        if (dist[matchR[it]] == dist[u] + 1) {
          if (dfs(matchR[it])) {
            matchL[u] = it;
            matchR[it] = u;
            return 1;
          }
        }
      }
      dist[u] = inf;
      return 0;
    }
    return 1;
  }
  long long match() {
    long long res = 0;
    while (bfs()) {
      for (long long i = 1; i <= n; i++) {
        if (!matchL[i]) {
          if (dfs(i)) res++;
        }
      }
    }
    return res;
  }
};
long long n, m;
vector<pair<long long, long long> > a[105];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m;
  long long cur = 1;
  Matching gg(4000);
  for (long long i = 1; i <= n; i++) {
    long long r;
    cin >> r;
    for (long long j = 2; j * j <= r; j++) {
      while (r % j == 0) {
        r /= j;
        a[i].emplace_back(j, cur);
        cur++;
      }
    }
    if (r != 1) {
      a[i].emplace_back(r, cur);
      cur++;
    }
  }
  for (long long i = 1; i <= m; i++) {
    long long u, v;
    cin >> u >> v;
    if (u % 2) swap(u, v);
    for (auto it : a[u]) {
      for (auto itt : a[v]) {
        if (it.first == itt.first) {
          gg.addEdge(it.second, itt.second);
        }
      }
    }
  }
  cout << gg.match();
  return 0;
}
