#include <bits/stdc++.h>
using namespace std;
map<int, int> mp[100];
int A[100];
int C[100];
class FlowDinics {
 private:
  struct edge {
    int to, back, cap;
    edge() { to = back = cap = -1; }
    edge(int _to, int _cap, int _back) : to(_to), cap(_cap), back(_back) {}
  };
  vector<vector<edge> > graph;
  vector<int> Layers, now;
  int n, source, sink;

 public:
  FlowDinics(int _n, int _source, int _sink)
      : n(_n), source(_source), sink(_sink) {
    graph.resize(n);
    Layers.resize(n);
    now.resize(n);
    for (int i = 0; i < (int)n; i++) graph[i].clear();
  }
  ~FlowDinics() {
    for (int i = 0; i < (int)n; i++) graph[i].clear();
  }
  void insert(int i, int j, int cap) {
    ;
    graph[i].push_back(edge(j, cap, graph[j].size()));
    graph[j].push_back(edge(i, 0, graph[i].size() - 1));
  }
  int bfs() {
    fill(Layers.begin(), Layers.end(), -1);
    Layers[sink] = 0;
    queue<int> Q;
    Q.push(sink);
    int top, from, to, cap, index;
    while (!Q.empty()) {
      top = Q.front();
      Q.pop();
      for (int i = 0; i < (int)graph[top].size(); i++) {
        from = graph[top][i].to;
        index = graph[top][i].back;
        if (graph[from][index].cap && Layers[from] == -1) {
          Layers[from] = Layers[top] + 1;
          Q.push(from);
        }
      }
    }
    return (Layers[source] != -1);
  }
  int dfs(int node, int val) {
    if (node == sink) {
      return val;
    }
    int flow, to, cap;
    for (int& start = now[node]; start < graph[node].size(); ++start) {
      to = graph[node][start].to;
      cap = graph[node][start].cap;
      if (cap > 0 && Layers[node] == Layers[to] + 1) {
        flow = dfs(to, min(val, cap));
        if (flow) {
          graph[node][start].cap -= flow;
          graph[to][graph[node][start].back].cap += flow;
          return flow;
        }
      }
    }
    return 0;
  }
  int flow() {
    int ret = 0, flow = 0;
    while (bfs()) {
      fill(now.begin(), now.end(), 0);
      while (flow = dfs(source, 100000000)) ret += flow;
    }
    return ret;
  }
};
void f(int id) {
  int x = A[id];
  while (x % 2 == 0) {
    x /= 2;
    mp[id][2]++;
  }
  for (int i = 3; i * i <= x; i += 2) {
    while (x % i == 0) {
      x /= i;
      mp[id][i]++;
    }
  }
  if (x > 1) mp[id][x]++;
  for (__typeof(mp[id].begin()) it(mp[id].begin()); it != mp[id].end(); it++)
    ;
  C[id] = mp[id].size();
  if (id) C[id] += C[id - 1];
}
int main() {
  int N, M;
  cin >> N >> M;
  for (int i = 0; i < (int)N; i++) {
    cin >> A[i];
    f(i);
  }
  FlowDinics G(2 + C[N - 1], 0, 1 + C[N - 1]);
  for (int i = 0; i < (int)N; i++) {
    if (i % 2 == 0) {
      int c = 0;
      if (i) c = C[i - 1];
      for (__typeof(mp[i].begin()) it(mp[i].begin()); it != mp[i].end(); it++) {
        c++;
        G.insert(0, c, it->second);
      }
    } else {
      int c = 0;
      if (i) c = C[i - 1];
      for (__typeof(mp[i].begin()) it(mp[i].begin()); it != mp[i].end(); it++) {
        c++;
        G.insert(c, C[N - 1] + 1, it->second);
      }
    }
  }
  for (int i = 0; i < (int)M; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    if (x % 2) swap(x, y);
    int c1 = 0;
    if (x) c1 = C[x - 1];
    for (__typeof(mp[x].begin()) it1(mp[x].begin()); it1 != mp[x].end();
         it1++) {
      c1++;
      int c2 = 0;
      if (y) c2 = C[y - 1];
      for (__typeof(mp[y].begin()) it2(mp[y].begin()); it2 != mp[y].end();
           it2++) {
        c2++;
        if (it2->first == it1->first) {
          G.insert(c1, c2, 100);
          ;
        }
      }
    }
  }
  cout << G.flow() << endl;
  return 0;
}
