#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
template <class T>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int maxn = 4000 + 7;
int n, m, t, T;
const int MAX_V = maxn;
struct edge {
  int to, cap, rev;
};
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];
void add_edge(int from, int to, int cap) {
  edge h;
  h.to = to;
  h.cap = cap;
  h.rev = G[to].size();
  G[from].push_back(h);
  h.to = from;
  h.cap = 0;
  h.rev = G[from].size() - 1;
  G[to].push_back(h);
}
void bfs(int s) {
  memset(level, -1, sizeof(level));
  queue<int> que;
  level[s] = 0;
  que.push(s);
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    for (int i = 0; i < ((int)(G[v]).size()); i++) {
      edge &e = G[v][i];
      if (e.cap > 0 && level[e.to] < 0) {
        level[e.to] = level[v] + 1;
        que.push(e.to);
      }
    }
  }
}
int dfs(int v, int t, int f) {
  if (v == t) return f;
  for (int &i = iter[v]; i < ((int)(G[v]).size()); i++) {
    edge &e = G[v][i];
    if (e.cap > 0 && level[v] < level[e.to]) {
      int d = dfs(e.to, t, min(f, e.cap));
      if (d > 0) {
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}
int max_flow(int s, int t) {
  int flow = 0;
  while (1) {
    bfs(s);
    if (level[t] < 0) return flow;
    memset(iter, 0, sizeof(iter));
    int f;
    while ((f = dfs(s, t, INF)) > 0) {
      flow += f;
    }
  }
}
vector<pair<int, int> > Q[100 + 7];
int a[100 + 7];
int cnt = 0;
void divide(int i) {
  int x = a[i];
  int y = sqrt(x);
  for (int j = 2; j <= y; j += 1) {
    while (x % j == 0) {
      Q[i].push_back(pair<int, int>(j, cnt++));
      x /= j;
    }
  }
  if (x != 1) Q[i].push_back(pair<int, int>(x, cnt++));
}
int x, y;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i += 1) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i += 1) divide(i);
  int S = cnt + n + 1, T = S + 1;
  for (int i = 1; i <= n; i += 1) {
    if (i & 1) {
      add_edge(S, i, INF);
      for (int j = 0; j < ((int)(Q[i]).size()); j++)
        add_edge(i, n + 1 + Q[i][j].second, 1);
    } else {
      add_edge(i, T, INF);
      for (int j = 0; j < ((int)(Q[i]).size()); j++)
        add_edge(n + 1 + Q[i][j].second, i, 1);
    }
  }
  while (m--) {
    scanf("%d%d", &x, &y);
    if (y & 1) swap(x, y);
    for (int i = 0; i < ((int)(Q[x]).size()); i += 1) {
      for (int j = 0; j < ((int)(Q[y]).size()); j += 1) {
        if (Q[x][i].first == Q[y][j].first) {
          add_edge(n + 1 + Q[x][i].second, n + 1 + Q[y][j].second, 1);
        }
      }
    }
  }
  printf("%d\n", max_flow(S, T));
  return 0;
}
