#include <bits/stdc++.h>
using namespace std;
const int MaxX = 100 + 5, LogN = 32 + 5, MaxN = 100 + 5, MaxM = 300 + 5,
          INF = 0x3fffffff;
int n, m, MaxFlow, Ans, S, T, Tot, a, b;
int A[MaxX], d[MaxN], Num[MaxN], B[MaxN][3];
inline int gmin(int a, int b) { return a < b ? a : b; }
inline int gmax(int a, int b) { return a > b ? a : b; }
struct Edge {
  int v, w;
  Edge *Next, *Other;
} E[MaxM * 2], *P = E, *Point[MaxN], *Last[MaxN];
inline void AddEdge(int x, int y, int z) {
  Edge *Q = ++P;
  ++P;
  P->v = y;
  P->w = z;
  P->Next = Point[x];
  Point[x] = P;
  P->Other = Q;
  Q->v = x;
  Q->w = 0;
  Q->Next = Point[y];
  Point[y] = Q;
  Q->Other = P;
}
int DFS(int Now, int Flow) {
  if (Now == T) return Flow;
  int ret = 0;
  for (Edge *j = Last[Now]; j; j = j->Next) {
    if (j->w && d[Now] == d[j->v] + 1) {
      Last[Now] = j;
      int p = DFS(j->v, gmin(j->w, Flow - ret));
      ret += p;
      j->w -= p;
      j->Other->w += p;
      if (ret == Flow) return ret;
    }
  }
  if (d[S] >= Tot) return ret;
  if (--Num[d[Now]] == 0) d[S] = Tot;
  ++Num[++d[Now]];
  Last[Now] = Point[Now];
  return ret;
}
void Solve(int x) {
  memset(E, 0, sizeof(E));
  P = E;
  memset(Point, 0, sizeof(Point));
  for (int i = 1; i <= n; ++i) {
    int Cnt = 0;
    while (A[i] % x == 0) {
      ++Cnt;
      A[i] /= x;
    }
    if (Cnt == 0) continue;
    if (i & 1)
      AddEdge(S, i, Cnt);
    else
      AddEdge(i, T, Cnt);
  }
  for (int i = 1; i <= m; ++i) AddEdge(B[i][0], B[i][1], INF);
  MaxFlow = 0;
  memset(d, 0, sizeof(d));
  memset(Num, 0, sizeof(Num));
  Num[0] = Tot;
  for (int i = 1; i <= Tot; ++i) Last[i] = Point[i];
  while (d[S] < Tot) MaxFlow += DFS(S, INF);
  Ans += MaxFlow;
}
int main() {
  scanf("%d%d", &n, &m);
  Ans = 0;
  for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &B[i][0], &B[i][1]);
    if (B[i][1] & 1) swap(B[i][0], B[i][1]);
  }
  S = n + 1;
  T = S + 1;
  Tot = T;
  for (int i = 1; i <= n; ++i) {
    int SQ = (int)sqrt(A[i] * 1.0);
    for (int j = 2; j <= SQ; ++j)
      if (A[i] % j == 0) Solve(j);
    if (A[i] > 1) Solve(A[i]);
  }
  printf("%d\n", Ans);
  return 0;
}
