#include <bits/stdc++.h>
using namespace std;
template <class T, class T2>
inline bool chkmax(T &x, const T2 &y) {
  return x < y ? x = y, 1 : 0;
}
template <class T, class T2>
inline bool chkmin(T &x, const T2 &y) {
  return x > y ? x = y, 1 : 0;
}
template <class T>
inline int sz(T a) {
  return a.size();
}
template <class T, class T2>
inline istream &operator>>(istream &is, pair<T, T2> &p) {
  is >> p.first >> p.second;
  if (p.first % 2 == 1) swap(p.first, p.second);
  return is;
}
template <class T, class T2>
inline ostream &operator<<(ostream &os, const pair<T, T2> &p) {
  os << p.first << ' ' << p.second;
  return os;
}
template <class T>
inline istream &operator>>(istream &is, vector<T> &v) {
  for (auto &curr : v) is >> curr;
  return is;
}
template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &v) {
  for (auto curr : v) os << curr << ' ';
  return os;
}
void inArray(int a[], const int &n) {
  for (int i = 0; i < n; i++) cin >> a[i];
}
void outArray(int a[], const int &n) {
  for (int i = 0; i < n; i++) cout << a[i] << ' ';
}
const int MAXA = 1e6;
const int MAXN = 100;
const int MAXM = 100;
int n, m;
vector<int> a;
vector<pair<int, int>> p;
vector<vector<int>> con;
bool primes[MAXA + 10];
int cap[MAXN + 10][MAXN + 10];
int path[MAXN + 10];
int mflow;
void input() {
  cin >> n >> m;
  a.resize(n);
  p.resize(m);
  con.resize(n + 2);
  cin >> a >> p;
}
void output() { cout << mflow << endl; }
void updatePrimes(int curr) {
  for (int i = curr * 2; i <= MAXA; i += curr) primes[i] = 1;
}
void findDivisors(int div) {
  for (int i = 0; i < n; i++) {
    cap[0][i + 1] = 0;
    cap[i + 1][n + 1] = 0;
    while (a[i] % div == 0) {
      a[i] /= div;
      if (i % 2)
        cap[0][i + 1]++;
      else
        cap[i + 1][n + 1]++;
    }
  }
}
void buildGraph() {
  for (int i = 2; i <= n; i += 2) {
    if (cap[0][i]) {
      cap[i][0] = 0;
      con[0].push_back(i);
      con[i].push_back(0);
    }
  }
  for (auto to : p) {
    if (cap[0][to.first] && cap[to.second][n + 1]) {
      cap[to.first][to.second] = MAXN;
      cap[to.second][to.first] = 0;
      con[to.first].push_back(to.second);
      con[to.second].push_back(to.first);
    }
  }
  for (int i = 1; i <= n; i += 2) {
    if (cap[i][n + 1]) {
      cap[n + 1][i] = 0;
      con[n + 1].push_back(i);
      con[i].push_back(n + 1);
    }
  }
}
void printGraph() {
  for (int i = 0; i <= n + 1; i++) {
    cout << i << " - ";
    for (auto id : con[i]) {
      cout << id << ' ';
    }
    cout << endl;
  }
}
void zeroing() {
  for (int i = 0; i < n; i++) con[i].clear();
  for (int i = 0; i <= n + 1; i++)
    for (int j = 0; j <= n + 1; j++) cap[i][j] = 0;
}
void zeroingPath() {
  for (int i = 0; i <= n + 1; i++) path[i] = -1;
}
int bfs() {
  zeroingPath();
  queue<pair<int, int>> q;
  q.push({0, MAXN});
  path[0] = -2;
  while (!q.empty()) {
    int curr = q.front().first;
    int fl = q.front().second;
    q.pop();
    for (auto id : con[curr]) {
      if (path[id] != -1 || cap[curr][id] == 0) continue;
      path[id] = curr;
      int nf = min(fl, cap[curr][id]);
      if (id == n + 1) return nf;
      q.push({id, nf});
    }
  }
  return 0;
}
int maxFlow() {
  int currflow = 0;
  int nf;
  while (nf = bfs()) {
    currflow += nf;
    int curr = n + 1;
    while (curr != 0) {
      cap[path[curr]][curr] -= nf;
      cap[curr][path[curr]] += nf;
      curr = path[curr];
    }
  }
  return currflow;
}
void solve() {
  mflow = 0;
  sort(p.begin(), p.end());
  for (int i = 2; i <= MAXA; i++) {
    if (!primes[i]) {
      zeroing();
      updatePrimes(i);
      findDivisors(i);
      buildGraph();
      mflow += maxFlow();
    }
  }
  for (int i = 0; i < n; i++) {
    if (a[i] != 1) {
      zeroing();
      updatePrimes(a[i]);
      findDivisors(a[i]);
      buildGraph();
      mflow += maxFlow();
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve();
  output();
  return 0;
}
