#include <bits/stdc++.h>
using std::vector;
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector<int> a(n);
  for (int& x : a) {
    scanf("%d", &x);
  }
  vector<vector<int>> next(n);
  for (int i = 0; i < (int)m; ++i) {
    int v1, v2;
    scanf("%d %d", &v1, &v2);
    --v1;
    --v2;
    next[v1].push_back(v2);
    next[v2].push_back(v1);
  }
  vector<vector<int>> devs(n);
  for (int i = 0; i < (int)n; ++i) {
    int x = a[i];
    for (int j = 2; j < (int)x / j + 1; ++j) {
      while (x % j == 0) {
        x /= j;
        devs[i].push_back(j);
      }
    }
    if (x > 1) {
      devs[i].push_back(x);
    };
    ;
  }
  const int MD = 31;
  vector<vector<vector<int>>> ni(n, vector<vector<int>>(MD));
  vector<vector<vector<int>>> nd(n, vector<vector<int>>(MD));
  for (int i = 0; i < (int)n; ++i) {
    for (int v : next[i]) {
      for (int j = 0; j < (int)devs[i].size(); ++j) {
        for (int k = 0; k < (int)devs[v].size(); ++k) {
          if (devs[i][j] == devs[v][k]) {
            ni[i][j].push_back(v);
            nd[i][j].push_back(k);
          }
        }
      }
    }
  }
  vector<vector<int>> mchi(n, vector<int>(MD, -1));
  vector<vector<int>> mchd(n, vector<int>(MD, -1));
  vector<vector<bool>> used;
  std::function<bool(int, int)> khun = [&](int i, int d) {
    if (used[i][d]) {
      return false;
    }
    used[i][d] = true;
    for (int j = 0; j < (int)ni[i][d].size(); ++j) {
      int ind = ni[i][d][j];
      int dev = nd[i][d][j];
      if (mchi[ind][dev] == -1 || khun(mchi[ind][dev], mchd[ind][dev])) {
        mchi[ind][dev] = i;
        mchd[ind][dev] = d;
        return true;
      }
    }
    return false;
  };
  int ans = 0;
  for (int i = 0; i < (int)n; ++i) {
    for (int j = 0; j < (int)devs[i].size(); ++j) {
      used.assign(n, vector<bool>(MD, false));
      if (khun(i, j)) {
        ++ans;
      }
    }
  }
  ans /= 2;
  printf("%d", ans);
  return 0;
}
