#include <bits/stdc++.h>
using namespace std;
int capacities[210][210];
int flowPassed[210][210];
vector<int> graph[210];
int parentsList[210];
int currentPathCapacity[210];
int bfs(int startNode, int endNode) {
  memset(parentsList, -1, sizeof(parentsList));
  memset(currentPathCapacity, 0, sizeof(currentPathCapacity));
  queue<int> q;
  q.push(startNode);
  parentsList[startNode] = -2;
  currentPathCapacity[startNode] = 2147483646;
  while (!q.empty()) {
    int currentNode = q.front();
    q.pop();
    for (int i = 0; i < graph[currentNode].size(); i++) {
      int to = graph[currentNode][i];
      if (parentsList[to] == -1 &&
          capacities[currentNode][to] - flowPassed[currentNode][to] > 0) {
        parentsList[to] = currentNode;
        currentPathCapacity[to] =
            min(currentPathCapacity[currentNode],
                capacities[currentNode][to] - flowPassed[currentNode][to]);
        if (to == endNode) return currentPathCapacity[endNode];
        q.push(to);
      }
    }
  }
  return 0;
}
int edmondsKarp(int startNode, int endNode) {
  int maxFlow = 0;
  while (true) {
    int flow = bfs(startNode, endNode);
    if (flow == 0) break;
    maxFlow += flow;
    int currentNode = endNode;
    while (currentNode != startNode) {
      int previousNode = parentsList[currentNode];
      flowPassed[previousNode][currentNode] += flow;
      flowPassed[currentNode][previousNode] -= flow;
      currentNode = previousNode;
    }
  }
  return maxFlow;
}
map<int, int> data[105], all;
int ara[105];
void func(int pos) {
  int number = ara[pos];
  int i, s = sqrt(number);
  for (i = 2; i <= s; i++) {
    if (number % i) continue;
    all[i] = 1;
    int k = 0;
    while (!(number % i)) {
      number /= i;
      k++;
    }
    data[pos][i] = k;
  }
  if (number > 1) {
    data[pos][number] = 1;
    all[number] = 1;
  }
  return;
}
void f(int number, int total) {
  memset(capacities, 0, sizeof(capacities));
  memset(flowPassed, 0, sizeof(flowPassed));
  int i, j;
  for (i = 1; i <= total; i++) {
    if (i % 2)
      capacities[0][i] = data[i][number];
    else
      capacities[i][total + 1] = data[i][number];
  }
  for (i = 1; i <= total; i += 2) {
    for (j = 0; j < graph[i].size(); j++)
      capacities[i][graph[i][j]] = 1000000000;
  }
  return;
}
int main() {
  int nodesCount, edgesCount, i;
  cin >> nodesCount >> edgesCount;
  for (i = 1; i <= nodesCount; i++) cin >> ara[i];
  int source, sink;
  source = 0;
  sink = nodesCount + 1;
  for (int edge = 0; edge < edgesCount; edge++) {
    int from, to;
    cin >> from >> to;
    graph[from].push_back(to);
    graph[to].push_back(from);
  }
  for (i = 1; i <= nodesCount; i += 2) {
    graph[0].push_back(i);
    graph[i].push_back(0);
  }
  for (i = 2; i <= nodesCount; i += 2) {
    graph[i].push_back(nodesCount + 1);
    graph[nodesCount + 1].push_back(i);
  }
  for (i = 1; i <= nodesCount; i++) func(i);
  int maxFlow = 0;
  map<int, int>::iterator it;
  it = all.begin();
  while (it != all.end()) {
    f(it->first, nodesCount);
    maxFlow += edmondsKarp(source, sink);
    it++;
  }
  cout << maxFlow << endl;
  return 0;
}
