#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2> p) {
  return out << '(' << p.first << ',' << p.second << ')';
}
template <class T1, class T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  return in >> p.first >> p.second;
}
template <class T>
istream& operator>>(istream& in, vector<T>& v) {
  for (T& x : v) in >> x;
  return in;
}
ostream& operator<<(ostream& out, const vector<string>& v) {
  for (const string& x : v) out << x << '\n';
  return out;
}
template <class T>
ostream& operator<<(ostream& out, const vector<vector<T>>& v) {
  for (const vector<T>& x : v) out << x << '\n';
  return out;
}
template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  for (const T& x : v) out << x << ' ';
  return out;
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
const int h = 1000000007;
long long gcd(long long a, long long b) {
  while (b != 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
class MaxFlow {
 private:
  struct FlowEdge {
    const int to;
    int capacity;
    FlowEdge(const int to, const int capacity) : to(to), capacity(capacity) {}
  };
  std::vector<std::vector<int>> adj;
  std::vector<FlowEdge> edges;
  std::vector<int> level;
  bool level_bfs(const int source, const int sink) {
    level = std::vector<int>(adj.size(), -1);
    std::queue<int> bfs_queue;
    level[source] = 0;
    bfs_queue.push(source);
    while (!bfs_queue.empty()) {
      const int node = bfs_queue.front();
      bfs_queue.pop();
      for (const int edge_ind : adj[node]) {
        const int to = edges[edge_ind].to;
        const int capacity = edges[edge_ind].capacity;
        if (capacity == 0 or level[to] != -1) {
          continue;
        }
        level[to] = level[node] + 1;
        bfs_queue.push(to);
      }
    }
    return level[sink] != -1;
  }
  int augment_flow(const int source, const int sink) {
    std::stack<std::pair<int, int>> dfs_stack;
    std::vector<int> par_edge_inds(adj.size(), -1);
    dfs_stack.push({source, std::numeric_limits<int>::max()});
    while (!dfs_stack.empty() and dfs_stack.top().first != sink) {
      const int cur = dfs_stack.top().first;
      const int flow = dfs_stack.top().second;
      dfs_stack.pop();
      for (const int edge_ind : adj[cur]) {
        const int to = edges[edge_ind].to;
        const int capacity = edges[edge_ind].capacity;
        if (capacity == 0 or level[to] != level[cur] + 1 or
            par_edge_inds[to] != -1) {
          continue;
        }
        par_edge_inds[to] = edge_ind;
        dfs_stack.push({to, std::min(flow, capacity)});
      }
    }
    const int flow = (dfs_stack.empty() ? 0 : dfs_stack.top().second);
    if (!dfs_stack.empty()) {
      int node = sink;
      while (node != source) {
        const int par_edge_ind = par_edge_inds[node];
        edges[par_edge_ind].capacity -= flow;
        edges[par_edge_ind ^ 1].capacity += flow;
        node = edges[par_edge_ind ^ 1].to;
      }
    }
    return flow;
  }

 public:
  MaxFlow(const int n) : adj(n) {}
  void add_edge(const int from, const int to, const int capacity) {
    adj[from].push_back(edges.size());
    edges.emplace_back(to, capacity);
    adj[to].push_back(edges.size());
    edges.emplace_back(from, 0);
  }
  int maxflow(const int source, const int sink) {
    int total_flow = 0;
    while (level_bfs(source, sink)) {
      while (const int flow = augment_flow(source, sink)) {
        total_flow += flow;
      }
    }
    return total_flow;
  }
};
std::vector<std::pair<int, int>> get_prime_factors(int n) {
  std::vector<std::pair<int, int>> ans;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      int cnt = 0;
      while (n % i == 0) {
        n /= i;
        cnt++;
      }
      ans.push_back({i, cnt});
    }
  }
  if (n != 1) {
    ans.push_back({n, 1});
  }
  return ans;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cerr.setstate(ios::failbit);
  int n, q;
  cin >> n >> q;
  vi v(n);
  cin >> v;
  vector<map<int, int>> m(n);
  vector<vector<pii>> vv(n);
  int c = 1;
  for (int i = (0); i < (n); i++) {
    vv[i] = get_prime_factors(v[i]);
    for (int j = (0); j < (vv[i].size()); j++) m[i][vv[i][j].first] = c + j;
    c += vv[i].size();
  }
  MaxFlow mf(c + 1);
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (vv[i].size()); j++) {
      if (i & 1)
        mf.add_edge(m[i][vv[i][j].first], c, vv[i][j].second);
      else
        mf.add_edge(0, m[i][vv[i][j].first], vv[i][j].second);
    }
  }
  while (q--) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    if (x & 1) swap(x, y);
    int g = gcd(v[x], v[y]);
    auto vp = get_prime_factors(g);
    for (auto p : vp) mf.add_edge(m[x][p.first], m[y][p.first], p.second);
  }
  cout << mf.maxflow(0, c);
}
