#include <bits/stdc++.h>
using namespace std;
long long int power(long long int x, long long int y, long long int m) {
  if (y == 0) return 1;
  long long int a = power(x, y / 2, m);
  if (y % 2) {
    return (a * ((a * x) % m)) % m;
  } else {
    return (a * a) % m;
  }
}
long long int mod_inverse(long long int x, long long int m) {
  return power(x, m - 2, m);
}
long long int fact(long long int n, long long int m) {
  if (n <= 1) return 1;
  return (fact(n - 1, m) * n) % m;
}
long long int ncr(long long int n, long long int r, long long int m) {
  if (r > n) return 0;
  long long int n1 = 1, d1 = 1, d2 = 1;
  n1 = fact(n, m);
  d1 = fact(r, m);
  d2 = fact(n - r, m);
  long long int ans = mod_inverse((d1 * d2) % m, m);
  ans = (ans * n1) % m;
  return ans;
}
class max_flow_push_relabel_improved {
 public:
  vector<vector<pair<int, int> > > g;
  int n;
  int s, t;
  vector<vector<int> > capacity, flow;
  vector<int> height, excess, seen;
  queue<int> excess_vertices;
  int INF = 1000000000;
  void build() {
    flow = vector<vector<int> >(n + 1, vector<int>(n + 1, 0));
    capacity = vector<vector<int> >(n + 1, vector<int>(n + 1, 0));
    height = vector<int>(n + 1, 0);
    excess = vector<int>(n + 1, 0);
    seen = vector<int>(n + 1, 1);
    height[s] = n;
    excess[s] = INF;
    for (int u = 1; u <= n; ++u) {
      for (auto pr : g[u]) {
        int v = pr.first, w = pr.second;
        capacity[u][v] += w;
      }
    }
  }
  max_flow_push_relabel_improved(vector<vector<pair<int, int> > > &gg, int nn,
                                 int ss, int tt) {
    g = gg;
    n = nn;
    s = ss;
    t = tt;
    build();
  }
  void push(int u, int v) {
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
    if (d && excess[v] == d) excess_vertices.push(v);
  }
  void relabel(int u) {
    int d = INF;
    for (int i = 1; i <= n; ++i) {
      if (capacity[u][i] - flow[u][i] > 0) d = min(d, height[i]);
    }
    if (d < INF) height[u] = d + 1;
  }
  vector<int> find_max_height_vertices() {
    vector<int> max_height;
    for (int i = 1; i <= n; ++i) {
      if (i == s || i == t || excess[i] == 0) continue;
      if (!max_height.empty() && height[i] > height[max_height[0]])
        max_height.clear();
      if (max_height.empty() || height[i] == height[max_height[0]])
        max_height.push_back(i);
    }
    return max_height;
  }
  int max_flow() {
    for (int i = 1; i <= n; ++i) {
      if (i != s) push(s, i);
    }
    vector<int> current;
    while (!(current = find_max_height_vertices()).empty()) {
      for (int i : current) {
        bool pushed = false;
        for (int j = 1; j <= n && excess[i]; j++) {
          if (capacity[i][j] - flow[i][j] > 0 && height[i] == height[j] + 1) {
            push(i, j);
            pushed = true;
          }
        }
        if (!pushed) {
          relabel(i);
          break;
        }
      }
    }
    int max_flow = 0;
    for (int i = 1; i <= n; ++i) {
      max_flow += flow[i][t];
    }
    return max_flow;
  }
};
class solver {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    int a[n + 1];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<vector<pair<int, int> > > g(n + 3);
    for (int i = 1; i <= m; ++i) {
      int u, v;
      cin >> u >> v;
      if (u % 2 == 1) swap(u, v);
      g[u].push_back({v, 1000000000});
    }
    int flow = 0;
    int mx = a[1];
    for (int i = 1; i <= n; ++i) mx = max(mx, a[i]);
    for (int p = 2; p * p <= mx; ++p) {
      vector<vector<pair<int, int> > > gg = g;
      mx = -1;
      for (int i = 1; i <= n; ++i) {
        if (a[i] % p != 0) continue;
        int cnt = 0;
        while (a[i] % p == 0) {
          cnt++;
          a[i] /= p;
        }
        if (i % 2 == 0) {
          gg[n + 1].push_back({i, cnt});
        } else {
          gg[i].push_back({n + 2, cnt});
        }
        if (mx == -1) mx = a[i];
        mx = max(mx, a[i]);
      }
      max_flow_push_relabel_improved o(gg, n + 2, n + 1, n + 2);
      flow += o.max_flow();
    }
    for (int j = 1; j <= n; ++j) {
      if (a[j] == 1) continue;
      int p = a[j];
      vector<vector<pair<int, int> > > gg = g;
      for (int i = 1; i <= n; ++i) {
        if (a[i] % p != 0) continue;
        int cnt = 0;
        while (a[i] % p == 0) {
          cnt++;
          a[i] /= p;
        }
        if (i % 2 == 0) {
          gg[n + 1].push_back({i, cnt});
        } else {
          gg[i].push_back({n + 2, cnt});
        }
      }
      max_flow_push_relabel_improved o(gg, n + 2, n + 1, n + 2);
      flow += o.max_flow();
    }
    cout << flow << '\n';
  }
};
int main() {
  int test = 1;
  while (test--) {
    solver o;
    o.solve();
  }
}
