#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxc = 105;
const int maxn = 1010;
int n, m;
int tot, head[maxn];
struct Edge {
  int to, next, cap, flow;
} edge[maxn * 4];
void addedge(int u, int v, int w) {
  edge[tot].to = v;
  edge[tot].cap = w;
  edge[tot].flow = 0;
  edge[tot].next = head[u];
  head[u] = tot++;
  edge[tot].to = u;
  edge[tot].cap = 0;
  edge[tot].flow = 0;
  edge[tot].next = head[v];
  head[v] = tot++;
}
int Q[maxn];
int gap[maxn], dep[maxn], cur[maxn];
void bfs(int s, int t) {
  memset(dep, -1, sizeof(dep));
  memset(gap, 0, sizeof(gap));
  gap[0] = 1;
  int fron = 0, rea = 0;
  dep[t] = 0;
  Q[rea++] = t;
  while (fron != rea) {
    int u = Q[fron++];
    for (int i = head[u]; ~i; i = edge[i].next) {
      int v = edge[i].to;
      if (dep[v] != -1) continue;
      Q[rea++] = v;
      dep[v] = dep[u] + 1;
      gap[dep[v]]++;
    }
  }
}
int S[maxn];
int sap(int s, int t, int N) {
  bfs(s, t);
  memcpy(cur, head, sizeof(head));
  int top = 0;
  int u = s;
  int ans = 0;
  while (dep[s] < N) {
    if (u == t) {
      int Min = inf;
      int inser;
      for (int i = 0; i < top; ++i) {
        if (Min > edge[S[i]].cap - edge[S[i]].flow) {
          Min = edge[S[i]].cap - edge[S[i]].flow;
          inser = i;
        }
      }
      for (int i = 0; i < top; ++i) {
        edge[S[i]].flow += Min;
        edge[S[i] ^ 1].flow -= Min;
      }
      ans += Min;
      top = inser;
      u = edge[S[top] ^ 1].to;
      continue;
    }
    bool flag = 0;
    int v;
    for (int i = cur[u]; ~i; i = edge[i].next) {
      v = edge[i].to;
      if (edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]) {
        flag = true;
        cur[u] = i;
        break;
      }
    }
    if (flag) {
      S[top++] = cur[u];
      u = v;
      continue;
    }
    int Min = N;
    for (int i = head[u]; ~i; i = edge[i].next) {
      if (edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) {
        Min = dep[edge[i].to];
        cur[u] = i;
      }
    }
    gap[dep[u]]--;
    if (!gap[dep[u]]) return ans;
    dep[u] = Min + 1;
    gap[dep[u]]++;
    if (u != s) u = edge[S[--top] ^ 1].to;
  }
  return ans;
}
vector<pair<int, int> > v[maxc];
int num[maxc][maxn];
void deal(int id, int x) {
  for (int i = 2; i <= sqrt(x) + 1; ++i) {
    if (x % i == 0) {
      while (x % i == 0) {
        int ns = v[id].size();
        if (!ns) {
          v[id].push_back(make_pair(i, 1));
        } else {
          if (v[id][ns - 1].first == i)
            v[id][ns - 1].second++;
          else
            v[id].push_back(make_pair(i, 1));
        }
        x /= i;
      }
    }
  }
  if (x != 1) {
    v[id].push_back(make_pair(x, 1));
  }
}
void init() {
  tot = 0;
  memset(head, -1, sizeof(head));
  for (int i = 0; i <= n; ++i) v[i].clear();
}
int main() {
  while (~scanf("%d %d", &n, &m)) {
    init();
    int val;
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &val);
      deal(i, val);
    }
    int cnt = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < v[i].size(); ++j) {
        num[i][j] = cnt++;
      }
    }
    int s = 0, t = cnt;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < v[i].size(); ++j) {
        int c = num[i][j];
        if (i % 2) {
          addedge(s, c, v[i][j].second);
        } else {
          addedge(c, t, v[i][j].second);
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      int x, y;
      scanf("%d %d", &x, &y);
      if (x % 2 == 0) {
        swap(x, y);
      }
      for (int i = 0; i < v[x].size(); ++i) {
        int xx = num[x][i];
        for (int j = 0; j < v[y].size(); ++j) {
          int yy = num[y][j];
          if (v[x][i].first == v[y][j].first) {
            addedge(xx, yy, inf);
          }
        }
      }
    }
    int ans = sap(s, t, cnt + 1);
    printf("%d\n", ans);
  }
  return 0;
}
