#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int M = 1000010;
const int N = 6666;
struct Edge {
  int v, next, c, f;
} edge[M];
struct Dinic {
  int head[N], cur[N], tol;
  void init() {
    tol = 0;
    memset(head, -1, sizeof(head));
  }
  void AddEdge(int u, int v, int w, int rw = 0) {
    edge[tol].v = v;
    edge[tol].c = w;
    edge[tol].f = 0;
    edge[tol].next = head[u];
    head[u] = tol++;
    edge[tol].v = u;
    edge[tol].c = rw;
    edge[tol].f = 0;
    edge[tol].next = head[v];
    head[v] = tol++;
  }
  int Q[N];
  int dep[N], sta[N];
  bool bfs(int s, int t) {
    int front = 0, tail = 0;
    memset(dep, -1, sizeof(dep));
    dep[s] = 0;
    Q[tail++] = s;
    while (front < tail) {
      int u = Q[front++];
      for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].v;
        if (edge[i].c > edge[i].f && dep[v] == -1) {
          dep[v] = dep[u] + 1;
          if (v == t) return 1;
          Q[tail++] = v;
        }
      }
    }
    return 0;
  }
  int dinic(int s, int t, int n) {
    int maxflow = 0;
    while (bfs(s, t)) {
      int u = s, tail = 0;
      for (int i = 0; i <= n; ++i) cur[i] = head[i];
      while (~cur[s]) {
        if (u == t) {
          int tp = INF;
          for (int i = tail - 1; i >= 0; --i)
            tp = min(tp, edge[sta[i]].c - edge[sta[i]].f);
          maxflow += tp;
          for (int i = tail - 1; i >= 0; --i) {
            edge[sta[i]].f += tp;
            edge[sta[i] ^ 1].f -= tp;
            if (edge[sta[i]].c - edge[sta[i]].f == 0) tail = i;
          }
          u = edge[sta[tail] ^ 1].v;
        } else if (cur[u] != -1 && edge[cur[u]].c > edge[cur[u]].f &&
                   dep[u] + 1 == dep[edge[cur[u]].v]) {
          sta[tail++] = cur[u];
          u = edge[cur[u]].v;
        } else {
          while (u != s && cur[u] == -1) u = edge[sta[--tail] ^ 1].v;
          cur[u] = edge[cur[u]].next;
        }
      }
    }
    return maxflow;
  }
} solver;
vector<int> prime;
bool a[100000 + 10] = {0};
int id[N][33], tot;
vector<int> pri[111];
void splite(int i, int x) {
  int cnt = 0;
  for (int j = 2; j * j <= x; j++)
    while (x % j == 0) {
      pri[i].push_back(j);
      id[i][cnt++] = ++tot;
      x /= j;
    }
  if (x > 1) {
    pri[i].push_back(x);
    id[i][cnt++] = ++tot;
  }
}
int main() {
  int n, m;
  tot = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    splite(i, x);
  }
  int s = 0, t = tot * 2 + 1;
  solver.init();
  for (int i = 1; i <= tot; i++) {
    solver.AddEdge(s, i, 1);
    solver.AddEdge(i + tot, t, 1);
  }
  while (m--) {
    int x, y;
    scanf("%d%d", &x, &y);
    for (int i = 0; i < pri[x].size(); i++) {
      for (int j = 0; j < pri[y].size(); j++)
        if (pri[x][i] == pri[y][j]) {
          solver.AddEdge(id[x][i], id[y][j] + tot, 1);
          solver.AddEdge(id[y][j], id[x][i] + tot, 1);
        }
    }
  }
  cout << solver.dinic(s, t, t + 1) / 2 << endl;
  return 0;
}
