#include <bits/stdc++.h>
using namespace std;
inline void in(int &n) {
  n = 0;
  int ch = getchar();
  int sign = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') sign = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
  }
  n = n * sign;
}
int a[4000 + 5];
vector<int> prime;
void pre() {
  int i, j, t;
  t = 2;
  prime.push_back(2);
  prime.push_back(3);
  for (i = 5; i * i <= 4000;) {
    if (a[i] == 0) {
      for (j = i * i; j <= 4000; j = j + i + i) {
        a[j] = 1;
      }
    }
    i = i + t;
    t = 6 - t;
  }
  t = 2;
  for (i = 5; i <= 4000;) {
    if (a[i] == 0) {
      prime.push_back(i);
    }
    i = i + t;
    t = 6 - t;
  }
}
vector<int> adj[3200];
int cap[3200][3200];
int find_path(int m1, int m2) {
  int v, i, prev, brkwhile = 0, from[3200], state[3200], path_cap;
  for (i = 0; i <= m1 + m2 + 1; i++) {
    from[i] = -1;
    state[i] = 0;
  }
  queue<int> Q;
  Q.push(0);
  state[0] = 2;
  while (!(Q.empty())) {
    v = Q.front();
    Q.pop();
    if (v == 0) {
      for (i = 1; i <= m1; i++) {
        if (cap[v][i] > 0 && state[i] == 0) {
          Q.push(i);
          state[i] = 2;
          from[i] = v;
        }
      }
    } else if (v >= 1 && v <= m1) {
      for (int tmp = 0; tmp < adj[v].size(); tmp++) {
        i = adj[v][tmp];
        if (cap[v][i] > 0 && state[i] == 0) {
          Q.push(i);
          state[i] = 2;
          from[i] = v;
        }
      }
    } else if (v >= m1 + 1 && v <= m1 + m2) {
      if (cap[v][m1 + m2 + 1] > 0) {
        Q.push(m1 + m2 + 1);
        state[m1 + m2 + 1] = 2;
        from[m1 + m2 + 1] = v;
        brkwhile = 1;
        break;
      }
      for (int tmp = 0; tmp < adj[v].size(); tmp++) {
        i = adj[v][tmp];
        if (cap[v][i] > 0 && state[i] == 0) {
          Q.push(i);
          state[i] = 2;
          from[i] = v;
        }
      }
    }
    if (brkwhile == 1) break;
  }
  v = m1 + m2 + 1;
  path_cap = (int(1e9));
  while (from[v] > -1) {
    prev = from[v];
    path_cap = min(path_cap, cap[prev][v]);
    v = prev;
  }
  v = m1 + m2 + 1;
  while (from[v] > -1) {
    prev = from[v];
    cap[prev][v] -= path_cap;
    cap[v][prev] += path_cap;
    v = prev;
  }
  if (path_cap == (int(1e9)))
    return 0;
  else
    return path_cap;
}
int max_flow(int m1, int m2) {
  int result = 0, path_capacity;
  while (1) {
    path_capacity = find_path(m1, m2);
    if (path_capacity == 0)
      break;
    else {
      result += path_capacity;
    }
  }
  return result;
}
int main() {
  pre();
  int n, M, i, j, k, l, m, curr, cnt, x, y, a, start, stop, idx, H[3200];
  vector<pair<int, int> > v[105], odd, even;
  in(n);
  in(M);
  for (i = 1; i <= n; i++) {
    in(a);
    if (i & 1) {
      odd.push_back(pair<int, int>(a, i));
    } else {
      even.push_back(pair<int, int>(a, i));
    }
  }
  curr = 0;
  for (i = 0; i < even.size(); i++) {
    a = even[i].first;
    idx = even[i].second;
    j = -1;
    while (a > 1) {
      j++;
      if (j == prime.size()) {
        cnt = 1;
        v[idx].push_back(pair<int, int>(curr + 1, curr + cnt));
        for (k = curr + 1; k <= curr + cnt; k++) {
          H[k] = a;
        }
        curr = curr + cnt;
        break;
      }
      if (a % prime[j] == 0) {
        cnt = 0;
        while (a % prime[j] == 0) {
          cnt++;
          a = a / prime[j];
        }
        v[idx].push_back(pair<int, int>(curr + 1, curr + cnt));
        for (k = curr + 1; k <= curr + cnt; k++) {
          H[k] = prime[j];
        }
        curr = curr + cnt;
      }
    }
  }
  start = curr;
  for (i = 0; i < odd.size(); i++) {
    a = odd[i].first;
    idx = odd[i].second;
    j = -1;
    while (a > 1) {
      j++;
      if (j == prime.size()) {
        cnt = 1;
        v[idx].push_back(pair<int, int>(curr + 1, curr + cnt));
        for (k = curr + 1; k <= curr + cnt; k++) {
          H[k] = a;
        }
        curr = curr + cnt;
        break;
      }
      if (a % prime[j] == 0) {
        cnt = 0;
        while (a % prime[j] == 0) {
          cnt++;
          a = a / prime[j];
        }
        v[idx].push_back(pair<int, int>(curr + 1, curr + cnt));
        for (k = curr + 1; k <= curr + cnt; k++) {
          H[k] = prime[j];
        }
        curr = curr + cnt;
      }
    }
  }
  stop = curr;
  for (i = 1; i <= start; i++) {
    cap[0][i] = 1;
  }
  for (i = start + 1; i <= stop; i++) {
    cap[i][stop + 1] = 1;
  }
  for (i = 1; i <= M; i++) {
    scanf("%d %d", &x, &y);
    ;
    if (x & 1) {
      swap(x, y);
    }
    for (j = 0; j < v[x].size(); j++) {
      for (k = 0; k < v[y].size(); k++) {
        for (l = v[x][j].first; l <= v[x][j].second; l++) {
          for (m = v[y][k].first; m <= v[y][k].second; m++) {
            if (H[l] == H[m]) {
              cap[l][m] = 1;
              adj[l].push_back(m);
              adj[m].push_back(l);
            }
          }
        }
      }
    }
  }
  int ans;
  ans = max_flow(start, stop - start);
  printf("%d\n", ans);
  return 0;
}
