#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / _gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
inline long long power(long long a, long long b) {
  long long multiply = 1;
  for (int i = (0); i < (b); i++) {
    multiply *= a;
  }
  return multiply;
}
int n, m, cost[205][205], resCost[205][205], parent[205];
vector<int> graph[205], primes, factsOf[105];
int u[105], v[105];
long long a[105];
bool status[100005], done[100], visited[205];
set<int> nodeU, nodeV;
void sieve() {
  for (int i = 1; i <= 100000; i++) status[i] = true;
  status[1] = false;
  for (int i = 4; i <= 100000; i += 2) status[i] = false;
  for (int i = 3; i <= sqrt(100000); i += 2) {
    for (int j = i * i; j <= 100000; j += (i + i)) {
      if (status[j]) status[j] = false;
    }
  }
  for (int i = 1; i <= 100000; i++) {
    if (status[i]) primes.push_back(i);
  }
}
void findPrimeFactors(long long x, int i) {
  for (int j = (0); j < (primes.size()); j++) {
    while (x % primes[j] == 0) {
      x /= primes[j];
      factsOf[i].push_back(primes[j]);
    }
  }
  if (x != 1) factsOf[i].push_back(x);
}
bool bfs(int s, int t) {
  memset(visited, 0, sizeof(visited));
  queue<int> Q;
  Q.push(s);
  visited[s] = true;
  memset(parent, -1, sizeof(parent));
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int j = (0); j < (graph[u].size()); j++) {
      int v = graph[u][j];
      if (!visited[v] && resCost[u][v] > 0) {
        Q.push(v);
        visited[v] = true;
        parent[v] = u;
      }
    }
  }
  return visited[t];
}
int maxFlow(int s, int t) {
  for (int i = 0; i <= n + 1; i++) {
    for (int j = 0; j <= n + 1; j++) resCost[i][j] = cost[i][j];
  }
  int max_flow = 0;
  while (bfs(s, t)) {
    int path_flow = INT_MAX;
    for (int v = t; v != s; v = parent[v]) {
      int u = parent[v];
      path_flow = min(path_flow, resCost[u][v]);
    }
    for (int v = t; v != s; v = parent[v]) {
      int u = parent[v];
      resCost[u][v] -= path_flow;
      resCost[v][u] += path_flow;
    }
    max_flow += path_flow;
  }
  return max_flow;
}
int main() {
  ios_base::sync_with_stdio(0);
  sieve();
  set<int> usePrimes;
  cin >> n >> m;
  for (int i = (1); i < (n + 1); i++) {
    cin >> a[i];
    findPrimeFactors(a[i], i);
    for (int j = (0); j < (factsOf[i].size()); j++)
      usePrimes.insert(factsOf[i][j]);
  }
  for (int i = (0); i < (m); i++) {
    cin >> u[i] >> v[i];
    if (v[i] % 2) swap(u[i], v[i]);
    graph[u[i]].push_back(v[i]);
    graph[v[i]].push_back(u[i]);
  }
  for (int i = (1); i < (n + 1); i++) {
    i % 2 ? graph[0].push_back(i) : graph[i].push_back(n + 1);
  }
  int ans = 0;
  for (__typeof((usePrimes).begin()) it = (usePrimes).begin();
       it != (usePrimes).end(); it++) {
    int nowPrime = *it;
    for (int i = 0; i <= n + 1; i++)
      for (int j = 0; j <= n + 1; j++) cost[i][j] = 0;
    for (int i = (0); i < (m); i++) {
      int cnt1 = 0, cnt2 = 0;
      for (int j = (0); j < (factsOf[u[i]].size()); j++) {
        if (factsOf[u[i]][j] == nowPrime) cnt1++;
      }
      cost[0][u[i]] = cnt1;
      for (int j = (0); j < (factsOf[v[i]].size()); j++) {
        if (factsOf[v[i]][j] == nowPrime) cnt2++;
      }
      cost[v[i]][n + 1] = cnt2;
      cost[u[i]][v[i]] = min(cnt1, cnt2);
    }
    ans += maxFlow(0, n + 1);
  }
  cout << ans << endl;
  return 0;
}
