#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
ostream &operator<<(ostream &O, pair<T1, T2> &t) {
  return O << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream &operator<<(ostream &O, vector<T> &t) {
  for (int _ = 0; _ < (int)t.size(); ++_) O << t[_] << " ";
  return O;
}
void dout() { cout << endl; }
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
  cout << H << " ";
  dout(T...);
}
inline void factorize(long long _n, vector<int> &_r) {
  long long _x;
  for (_x = 2; _n > 1;) {
    while (_n % _x == 0) {
      _r.push_back(_x);
      _n /= _x;
    }
    _x += 1 + (_x > 2);
    if (_x * _x > _n) _x = _n;
  }
}
template <typename T>
class FlowEdge {
  int u;
  T c, f;

 public:
  FlowEdge() : u(-1), c(0), f(0){};
  FlowEdge(int _u, T _c = 1) : u(_u), c(_c), f(0){};
  static int type() { return 2; }
  static int type_w() { return 1; }
  static T type_f() { return new T; }
  int get_u() { return u; }
  void set_u(int _u) { u = _u; }
  T get_c() { return c; }
  void set_c(T _c) { c = _c; }
  T get_f() { return f; }
  void set_f(T _f) { f = _f; }
  int get_w() { return 1; }
  void push(T p) { f += p; }
};
template <typename T>
class Graph {
 public:
  int N;
  vector<int> *g;
  vector<T> ve;
  Graph(int _N) {
    N = _N;
    g = new vector<int>[N];
  }
  ~Graph() { delete[] g; }
  static int type() { return T::type(); }
  static decltype(T::type_w()) type_w() { return T::type_w(); }
  static decltype(T::type_f()) type_f() { return T::type_f(); }
  void addEdge(int v, int u) {
    T e(u);
    g[v].push_back(ve.size());
    ve.push_back(e);
  }
  template <typename T1>
  void addEdge(int v, int u, T1 t) {
    T e(u, t);
    g[v].push_back(ve.size());
    ve.push_back(e);
  }
  template <typename T1, typename T2>
  void addEdge(int v, int u, T1 w, T2 c) {
    T e(u, w, c);
    g[v].push_back(ve.size());
    ve.push_back(e);
  }
  template <typename T1>
  void addFlowEdge(int v, int u, T1 c) {
    T e1(u, c);
    g[v].push_back(ve.size());
    ve.push_back(e1);
    T e2(v, 0);
    g[u].push_back(ve.size());
    ve.push_back(e2);
  }
  void clearFlow() {
    for (int i = 0; i < (int)ve.size(); ++i) {
      ve[i].set_f(0);
    }
  }
  void addBiEdge(int v, int u) {
    addEdge(v, u);
    addEdge(u, v);
  }
  template <typename T1>
  void addBiEdge(int v, int u, T1 t) {
    addEdge(v, u, t);
    addEdge(u, v, t);
  }
  template <typename T1, typename T2>
  void addBiEdge(int v, int u, T1 w, T2 c) {
    addEdge(v, u, w, c);
    addEdge(u, v, w, c);
  }
  void remEdge(int v, int u) {
    g[v].pop_back();
    ve.pop_back();
  }
  void remBiEdge(int v, int u) {
    remEdge(v, u);
    remEdge(u, v);
  }
  bool isSparse() { return !N || ve.size() * 100 / N < N; }
};
class {
  vector<int> d;
  vector<int> ptr;
  int S, T;

 public:
  template <typename U>
  decltype(U::type_f()) operator()(U &graph, int s, int t) {
    S = s;
    T = t;
    decltype(U::type_f()) flow = 0, f;
    while (bfs(graph)) {
      ptr.assign(graph.N, 0);
      while ((f = dfs(graph, S)) > (0.00000001)) flow += f;
    }
    return flow;
  }
  template <typename U>
  bool bfs(U &graph) {
    queue<int> q;
    q.push(S);
    d.assign(graph.N, -1);
    d[S] = 0;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto id : graph.g[v]) {
        auto e = graph.ve[id];
        if (d[e.get_u()] == -1 && e.get_f() < e.get_c())
          d[e.get_u()] = d[v] + 1, q.push(e.get_u());
      }
    }
    return d[T] != -1;
  }
  template <typename U>
  decltype(U::type_f()) dfs(U &graph, int v,
                            decltype(U::type_f()) f = (2147483647)) {
    if (f < (0.00000001)) return 0;
    if (v == T) return f;
    for (; ptr[v] < (int)graph.g[v].size(); ++ptr[v]) {
      int id = graph.g[v][ptr[v]];
      auto e = graph.ve[id];
      if (d[e.get_u()] != d[v] + 1) continue;
      auto p = dfs(graph, e.get_u(), min(f, e.get_c() - e.get_f()));
      if (p > (0.00000001)) {
        graph.ve[id].push(p);
        graph.ve[id ^ 1].push(-p);
        return p;
      }
    }
    return 0;
  }
} MaxFlow;
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int mas[109];
  vector<int> mm[109];
  set<int> pr;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &mas[i]);
    int a = mas[i];
    factorize(a, mm[i]);
    for (auto e : mm[i]) pr.insert(e);
  }
  Graph<FlowEdge<int> > g(n + 2);
  for (int i = 1; i <= n; ++i) {
    if (i % 2 == 0)
      g.addFlowEdge(0, i, 0);
    else
      g.addFlowEdge(i, n + 1, 0);
  }
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (a % 2 == 0)
      g.addFlowEdge(a, b, (2147483647));
    else
      g.addFlowEdge(b, a, (2147483647));
  }
  int res = 0;
  for (auto e : pr) {
    for (int i = 0; i < n; ++i) {
      int cnt = count(mm[i].begin(), mm[i].end(), e);
      g.ve[2 * i].set_c(cnt);
    }
    g.clearFlow();
    res += MaxFlow(g, 0, n + 1);
  }
  cout << res;
  return 0;
}
int cpp4cf_main() {
  freopen("E.cpp", "r", stdin);
  char s[99];
  bool f;
  while (true) {
    cin >> s;
    if (cin.eof()) break;
    if (strstr(s, "/*")) {
      cin >> s;
      if (strstr(s, "Test")) {
        cin >> s;
        if (strstr(s, "on")) {
          cout << "Output: ";
          cpp4cf_main();
          cout << "\nAnswer: ";
          f = false;
          while (true) {
            cin >> s;
            if (strstr(s, "*/")) break;
            if (strstr(s, "//")) {
              if (f)
                cout << endl;
              else
                f = true;
            } else
              cout << s << " ";
          }
          cout << "\n\n";
        }
      }
    }
  }
  return 0;
}
