#include <bits/stdc++.h>
template <typename FlowSize>
class DinicFlow {
  struct Edge {
    std::size_t from, to;
    FlowSize cap;
    FlowSize flow;
  };

 public:
  DinicFlow(std::size_t n) : g(n), queue(n), pointer(n), used(n), d(n) {}
  void addEdge(std::size_t from, std::size_t to, FlowSize capacity) {
    return addTwoSidedEdge(from, to, capacity, 0);
  }
  void addTwoSidedEdge(std::size_t from, std::size_t to, FlowSize capacity,
                       FlowSize backwardCapacity) {
    Edge edge = {from, to, capacity, 0};
    g[from].push_back(edges.size());
    edges.push_back(edge);
    Edge backwardEdge = {to, from, backwardCapacity, 0};
    g[to].push_back(edges.size());
    edges.push_back(backwardEdge);
  }
  Edge getEdge(std::size_t id) { return edges[id]; }
  FlowSize findFlow(std::size_t from, std::size_t to,
                    FlowSize infinity = std::numeric_limits<FlowSize>::max()) {
    ;
    FlowSize flow = 0;
    while (bfs(from, to)) {
      memset(&pointer[0], 0, sizeof(std::size_t) * pointer.size());
      while (FlowSize pushed = dfs(from, to, infinity)) {
        flow += pushed;
      }
    }
    return flow;
  }

 private:
  bool bfs(std::size_t from, std::size_t to) {
    memset(&used[0], false, sizeof(char) * used.size());
    std::size_t qh = 0, qt = 0;
    queue[qt++] = from;
    used[from] = true;
    while (qh != qt) {
      std::size_t v = queue[qh++];
      for (std::size_t id : g[v]) {
        Edge& edge = edges[id];
        if (used[edge.to]) {
          continue;
        }
        if (edge.cap == edge.flow) {
          continue;
        }
        used[edge.to] = true;
        d[edge.to] = d[v] + 1;
        queue[qt++] = edge.to;
      }
    }
    return used[to];
  }
  FlowSize dfs(std::size_t v, std::size_t to, FlowSize mx) {
    if (mx == 0) {
      return 0;
    }
    if (v == to) {
      return mx;
    }
    for (std::size_t& i = pointer[v]; i < g[v].size(); ++i) {
      std::size_t id = g[v][i];
      Edge& e = edges[id];
      if (d[e.to] == d[v] + 1) {
        if (FlowSize pushed = dfs(e.to, to, std::min(mx, e.cap - e.flow))) {
          e.flow += pushed;
          edges[id ^ 1].flow -= pushed;
          return pushed;
        }
      }
    }
    return 0;
  }
  std::vector<std::vector<std::size_t>> g;
  std::vector<Edge> edges;
  std::vector<std::size_t> queue;
  std::vector<std::size_t> pointer;
  std::vector<char> used;
  std::vector<FlowSize> d;
};
using namespace std;
class TaskC {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int n, m;
    in >> n >> m;
    int s = 2 * n;
    int t = s + 1;
    std::vector<int> a(n);
    std::map<int, int> cnt;
    for (int i = 0; i < n; ++i) {
      in >> a[i];
      int c = a[i];
      for (int j = 2; j * j <= c; ++j) {
        if (c % j == 0) {
          ++cnt[j];
          while (c % j == 0) {
            c /= j;
          }
        }
      }
      if (c != 1) ++cnt[c];
    }
    std::vector<int> aa(m), bb(m);
    for (int i = 0; i < m; ++i) {
      in >> aa[i] >> bb[i];
      --aa[i];
      --bb[i];
    }
    long long res = 0;
    for (auto x : cnt) {
      if (x.second < 2) continue;
      DinicFlow<long long> dinic(2 * n + 2);
      for (int i = 0; i < m; ++i) {
        if (aa[i] % 2 == 0) {
          dinic.addEdge(aa[i] + n, bb[i], 1000);
        } else {
          dinic.addEdge(bb[i] + n, aa[i], 1000);
        }
      }
      for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) {
          dinic.addEdge(s, i, 1000);
        } else
          dinic.addEdge(i + n, t, 1000);
        int z = 0;
        while (a[i] % x.first == 0) {
          ++z;
          a[i] /= x.first;
        }
        if (z) {
          dinic.addEdge(i, i + n, z);
        }
      }
      res += dinic.findFlow(s, t);
    }
    out << res;
  }
};
int main() {
  std::cin.sync_with_stdio(false);
  std::cin.tie(0);
  std::cout << std::fixed;
  std::cout.precision(20);
  TaskC solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}
