#include <bits/stdc++.h>
using namespace std;
template <class NumT = int>
struct Edge {
  int a, b;
  NumT w;
  Edge(int _a, int _b) : a(_a), b(_b), w(1) {}
  Edge(int _a, int _b, NumT _w) : a(_a), b(_b), w(_w) {}
};
template <class NumT = int>
struct Flow {
  int size, source, sink;
  vector<vector<NumT> > adj;
  vector<Edge<NumT> > e;
  vector<int> p;
  vector<bool> visited;
  vector<int> dist;
  vector<int> used;
  Flow(int _size) : size(_size) {
    adj = vector<vector<NumT> >(_size);
    source = 0, sink = _size - 1;
  }
  void setup(const int s, const int t) {
    source = s;
    sink = t;
  }
  void add_edge(const int u, const int v, const NumT weight) {
    adj[u].push_back((int)e.size());
    e.push_back(Edge<NumT>(u, v, weight));
    adj[v].push_back((int)e.size());
    e.push_back(Edge<NumT>(v, u, (NumT)0));
  }
  void add_undirected_edge(const int u, const int v, const NumT weight) {
    add_edge(u, v, weight);
    add_edge(v, u, weight);
  }
  void add_bipartite_edge(const int u, const int v) {
    if (adj[u].empty()) add_edge(source, u, 1);
    if (adj[v].empty()) add_edge(v, sink, 1);
    add_edge(u, v, 1);
  }
  NumT _augmenting_ford(const int u, const NumT bottle) {
    if (visited[u]) return (NumT)0;
    visited[u] = true;
    if (u == sink) return bottle;
    for (int i = 0; i < (int)adj[u].size(); i++) {
      int x = adj[u][i];
      if (e[x].w > (NumT)0) {
        NumT cf = _augmenting_ford(e[x].b, min(bottle, e[x].w));
        if (cf > 0) {
          e[x].w -= cf;
          e[x ^ 1].w += cf;
          return cf;
        }
      }
    }
    return (NumT)0;
  }
  NumT augmenting_ford() {
    visited.assign(size, false);
    return _augmenting_ford(source, numeric_limits<NumT>::max());
  }
  NumT _augmenting_edmonds(const int u, const NumT bottle) {
    if (!bottle) return (NumT)0;
    if (u == source) {
      return bottle;
    } else if (p[u] != -1) {
      int x = p[u];
      NumT cf = _augmenting_edmonds(e[x].a, min(bottle, e[x].w));
      e[x].w -= cf;
      e[x ^ 1].w += cf;
      return cf;
    }
    return (NumT)0;
  }
  void _augmenting_bfs() {
    p.assign(size, -1);
    vector<int> dist(size, -1);
    dist[source] = 0;
    queue<int> q;
    q.push(source);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u == sink) break;
      for (int i = 0; i < (int)adj[u].size(); i++) {
        int x = adj[u][i];
        if (e[x].w > 0 && dist[e[x].b] == -1)
          dist[e[x].b] = dist[u] + 1, q.push(e[x].b), p[e[x].b] = x;
      }
    }
  }
  NumT augmenting_edmonds() {
    _augmenting_bfs();
    return _augmenting_edmonds(sink, numeric_limits<NumT>::max());
  }
  bool _layered_bfs() {
    dist.assign(size, -1);
    dist[source] = 0;
    queue<int> q;
    q.push(source);
    while (!q.empty() && dist[sink] == -1) {
      int u = q.front();
      q.pop();
      for (int i = 0; i < (int)adj[u].size(); i++) {
        int x = adj[u][i];
        if (dist[e[x].b] == -1 && e[x].w > 0) {
          dist[e[x].b] = dist[u] + 1;
          q.push(e[x].b);
        }
      }
    }
    return dist[sink] != -1;
  }
  NumT _augmenting_dinic(const int u, const NumT bottle) {
    if (!bottle) return (NumT)0;
    if (u == sink) return bottle;
    for (int& i = used[u]; i < (int)adj[u].size(); i++) {
      int x = adj[u][i];
      if (dist[e[x].b] != dist[u] + 1) continue;
      NumT cf = _augmenting_dinic(e[x].b, min(bottle, e[x].w));
      e[x].w -= cf;
      e[x ^ 1].w += cf;
      if (cf) return cf;
    }
    return (NumT)0;
  }
  NumT blocking_flow() {
    if (!_layered_bfs()) return (NumT)0;
    used.assign(size, 0);
    NumT aug, flow = 0;
    while ((aug = _augmenting_dinic(source, numeric_limits<NumT>::max())))
      flow += aug;
    return flow;
  }
  NumT max_flow_ford() {
    NumT aug, flow = 0;
    while ((aug = augmenting_ford())) flow += aug;
    return flow;
  }
  NumT max_flow_edmonds() {
    NumT aug, flow = 0;
    while ((aug = augmenting_edmonds())) flow += aug;
    return flow;
  }
  NumT max_flow_dinic() {
    NumT aug, flow = 0;
    while ((aug = blocking_flow())) flow += aug;
    return flow;
  }
};
struct MCBM {
  int size;
  vector<vector<int> > adj;
  vector<int> visited, match;
  MCBM(int _size) : size(_size) {
    adj = vector<vector<int> >(_size);
    match = vector<int>(_size);
  }
  MCBM(vector<vector<int> > _adj) : adj(_adj), size(_adj.size()) {
    match = vector<int>(_adj.size());
  }
  void add_edge(const int u, const int v) { adj[u].push_back(v); }
  int _augmenting(const int u) {
    if (visited[u]) return 0;
    visited[u] = true;
    for (int i = 0; i < (int)adj.size(); i++) {
      int v = adj[u][i];
      if (match[v] == -1 || _augmenting(match[v])) {
        match[v] = u;
        return 1;
      }
    }
    return 0;
  }
  int augmenting(const int u) {
    visited.assign(size, false);
    return _augmenting(u);
  }
  int max_matching_kuhn() {
    int matching = 0;
    for (int i = 0; i < size; i++) matching += augmenting(i);
    return matching;
  }
};
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<vector<pair<int, int> > > factors(n, vector<pair<int, int> >());
  int size = 1;
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    for (int p = 2; p * p <= a; p++) {
      while (a % p == 0) {
        factors[i].push_back(pair<int, int>(p, size++));
        a /= p;
      }
    }
    if (a > 1) factors[i].push_back(pair<int, int>(a, size++));
  }
  Flow<int> matching(size + 2);
  for (int k = 0; k < m; k++) {
    int i, j;
    scanf("%d%d", &i, &j);
    i--, j--;
    if (j % 2 == 0) swap(i, j);
    for (pair<int, int> x : factors[i]) {
      for (pair<int, int> y : factors[j]) {
        if (x.first == y.first) {
          matching.add_bipartite_edge(x.second, y.second);
        }
      }
    }
  }
  printf("%d\n", matching.max_flow_dinic());
  return 0;
}
