#include <bits/stdc++.h>
using namespace std;
const int N = 300009;
const int mod = 1000000007;
template <class T>
struct Edge {
  int from, to, index;
  T cap, flow;
  Edge(int from, int to, T cap, T flow, int index)
      : from(from), to(to), cap(cap), flow(flow), index(index) {}
};
template <class T>
struct PushRelabel {
  int n;
  vector<vector<Edge<T>>> adj;
  vector<T> excess;
  vector<int> dist, count;
  vector<bool> active;
  vector<vector<int>> B;
  int b;
  queue<int> Q;
  PushRelabel(int n) : n(n), adj(n) {}
  void AddEdge(int from, int to, int cap) {
    adj[from].push_back(Edge<T>(from, to, cap, 0, adj[to].size()));
    if (from == to) {
      adj[from].back().index++;
    }
    adj[to].push_back(Edge<T>(to, from, 0, 0, adj[from].size() - 1));
  }
  void Enqueue(int v) {
    if (!active[v] && excess[v] > 0 && dist[v] < n) {
      active[v] = true;
      B[dist[v]].push_back(v);
      b = max(b, dist[v]);
    }
  }
  void Push(Edge<T>& e) {
    T amt = min(excess[e.from], e.cap - e.flow);
    if (dist[e.from] == dist[e.to] + 1 && amt > T(0)) {
      e.flow += amt;
      adj[e.to][e.index].flow -= amt;
      excess[e.to] += amt;
      excess[e.from] -= amt;
      Enqueue(e.to);
    }
  }
  void Gap(int k) {
    for (int v = 0; v < n; v++)
      if (dist[v] >= k) {
        count[dist[v]]--;
        dist[v] = max(dist[v], n);
        count[dist[v]]++;
        Enqueue(v);
      }
  }
  void Relabel(int v) {
    count[dist[v]]--;
    dist[v] = n;
    for (auto e : adj[v])
      if (e.cap - e.flow > 0) {
        dist[v] = min(dist[v], dist[e.to] + 1);
      }
    count[dist[v]]++;
    Enqueue(v);
  }
  void Discharge(int v) {
    for (auto& e : adj[v]) {
      if (excess[v] > 0) {
        Push(e);
      } else {
        break;
      }
    }
    if (excess[v] > 0) {
      if (count[dist[v]] == 1) {
        Gap(dist[v]);
      } else {
        Relabel(v);
      }
    }
  }
  T GetMaxFlow(int s, int t) {
    dist = vector<int>(n, 0), excess = vector<T>(n, 0),
    count = vector<int>(n + 1, 0), active = vector<bool>(n, false),
    B = vector<vector<int>>(n), b = 0;
    for (auto& e : adj[s]) {
      excess[s] += e.cap;
    }
    count[0] = n;
    Enqueue(s);
    active[t] = true;
    while (b >= 0) {
      if (!B[b].empty()) {
        int v = B[b].back();
        B[b].pop_back();
        active[v] = false;
        Discharge(v);
      } else {
        b--;
      }
    }
    return excess[t];
  }
  T GetMinCut(int s, int t, vector<int>& cut);
};
void pre() {}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin.exceptions(cin.failbit);
  ;
  pre();
  int n, m;
  cin >> n >> m;
  set<int> s;
  vector<int> a(n);
  for (auto& it : a) cin >> it;
  vector<vector<int>> v(n + 1);
  int x, y;
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  int second = 0;
  int T = n + 1;
  int tmp;
  for (int j = 0; j < (n); ++j) {
    tmp = a[j];
    for (int i = 2; (i * i) <= a[j]; i++) {
      if ((a[j] % i) == 0) {
        s.insert(i);
        while (a[j] % i == 0) a[j] /= i;
      }
    }
    if (a[j] > 1) {
      s.insert(a[j]);
    }
    a[j] = tmp;
  }
  int ans = 0, temp, res;
  for (auto& it : s) {
    struct PushRelabel<int>* X = new PushRelabel<int>(n + 2);
    for (int i = 0; i < n; i++) {
      res = 0;
      temp = a[i];
      while (temp % it == 0) {
        temp /= it;
        res++;
      }
      if (i % 2 == 0) {
        X->AddEdge(0, i + 1, res);
      } else {
        X->AddEdge(i + 1, n + 1, res);
      }
      for (auto& it : v[i + 1]) {
        if (it % 2 == 0) {
          X->AddEdge(i + 1, it, 100);
        }
      }
    }
    ans += X->GetMaxFlow(0, n + 1);
  }
  cout << ans << "\n";
  return 0;
}
