#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
long long pwr(long long a, long long b, long long mod) {
  if (b == 0) return 1;
  long long temp = pwr(a, b / 2, mod);
  temp = (temp * temp) % mod;
  if (b & 1) temp = (temp * a) % mod;
  return temp;
}
long long pwr(long long a, long long b) {
  if (b == 0) return 1;
  long long temp = pwr(a, b / 2);
  temp = (temp * temp);
  if (b & 1) temp = (temp * a);
  return temp;
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
long long modularInverse(long long a, long long m) { return pwr(a, m - 2, m); }
bool *isPrime;
void generatePrimeSieve(const int lim) {
  isPrime = (bool *)malloc(lim + 1);
  memset(isPrime, true, lim + 1);
  isPrime[0] = false;
  isPrime[1] = false;
  for (int i = 2; i <= lim; ++i)
    if (isPrime[i])
      for (int j = i + i; j <= lim; j += i) isPrime[j] = false;
}
vector<vector<int> > identityMatrix;
vector<vector<int> > mul(const vector<vector<int> > &a,
                         const vector<vector<int> > &b) {
  int n = a.size();
  vector<vector<int> > ans(n, vector<int>(n));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int k = 0; k < n; ++k) {
        ans[i][j] += ((long long)a[i][k] * b[k][j]) % mod;
        ans[i][j] %= mod;
      }
    }
  }
  return ans;
}
vector<vector<int> > pwr(const vector<vector<int> > &a, long long n) {
  if (n == 0) {
    assert(false);
    return identityMatrix;
  }
  if (n == 1) return a;
  vector<vector<int> > tmp = pwr(a, n / 2);
  tmp = mul(tmp, tmp);
  if (n & 1) tmp = mul(a, tmp);
  return tmp;
}
struct Edge {
  int u, v, flow, capacity;
  Edge() {}
  Edge(int u, int v, int flow, int capacity) {
    this->u = u;
    this->v = v;
    this->flow = flow;
    this->capacity = capacity;
  }
};
vector<Edge> e;
vector<vector<int> > G;
int n, m;
int source, sink;
int dist[5001];
int ptr[5001];
bool findPath() {
  memset(dist, -1, sizeof(dist));
  dist[source] = 0;
  queue<int> Q;
  Q.push(source);
  while (!Q.empty()) {
    int u = Q.front();
    assert(dist[u] >= 0);
    Q.pop();
    for (int i = 0; i < G[u].size(); ++i) {
      int ID = G[u][i];
      int v = e[ID].v;
      if ((dist[v] == -1) && e[ID].flow < e[ID].capacity) {
        dist[v] = dist[u] + 1;
        Q.push(v);
      }
    }
  }
  return dist[sink] != -1;
}
int dfs(int u, int flow) {
  if (flow == 0) return 0;
  if (u == sink) return flow;
  for (; ptr[u] < G[u].size(); ++ptr[u]) {
    int ID = G[u][ptr[u]];
    int v = e[ID].v;
    if (dist[v] != dist[u] + 1) continue;
    int pushed = dfs(v, min(flow, e[ID].capacity - e[ID].flow));
    if (pushed) {
      e[ID].flow += pushed;
      e[ID ^ 1].flow -= pushed;
      return pushed;
    }
  }
  return 0;
}
long long dinics() {
  long long flow = 0;
  while (findPath()) {
    memset(ptr, 0, sizeof ptr);
    while (int pushed = dfs(source, 1e9)) flow += pushed;
  }
  return flow;
}
void addEdge(int u, int v, int capacity) {
  G[u].push_back(e.size());
  e.push_back(Edge(u, v, 0, capacity));
  G[v].push_back(e.size());
  e.push_back(Edge(v, u, 0, 0));
}
int a[1231];
int curr;
map<int, pair<int, int> > M[500];
void factorize(int u) {
  int x = a[u];
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      int base = i;
      int power = 0;
      while (x % i == 0) {
        x /= i;
        ++power;
      }
      M[u][base] = pair<int, int>(power, curr++);
    }
  }
  if (x != 1) M[u][x] = pair<int, int>(1, curr++);
}
int main() {
  std::ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  source = 0;
  sink = n + 1;
  curr = n + 2;
  G.resize(1e6);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    factorize(i);
    if (i % 2) {
      addEdge(source, i, (1000000007));
      for (map<int, pair<int, int> >::iterator j = M[i].begin();
           j != M[i].end(); ++j) {
        int cap = (*j).second.first;
        int id = (*j).second.second;
        addEdge(i, id, cap);
      }
    } else {
      addEdge(i, sink, (1000000007));
      for (map<int, pair<int, int> >::iterator j = M[i].begin();
           j != M[i].end(); ++j) {
        int cap = (*j).second.first;
        int id = (*j).second.second;
        addEdge(id, i, cap);
      }
    }
  }
  while (m--) {
    int u, v;
    cin >> u >> v;
    for (map<int, pair<int, int> >::iterator i = M[u].begin(); i != M[u].end();
         ++i) {
      int key = (*i).first;
      if (M[v].find(key) == M[v].end()) continue;
      int id1 = M[u][key].second;
      int id2 = M[v][key].second;
      if (u & 1)
        addEdge(id1, id2, (1000000007));
      else
        addEdge(id2, id1, (1000000007));
    }
  }
  cout << dinics();
}
