#include <bits/stdc++.h>
using namespace std;
inline int rei() {
  int x;
  cin >> x;
  return x;
}
inline long long rel() {
  long long x;
  cin >> x;
  return x;
}
inline string res() {
  string x;
  cin >> x;
  return x;
}
struct MaxFlow {
  struct edge {
    int to, cap, rev;
  };
  int V;
  vector<vector<edge>> G;
  vector<int> itr, level;
  MaxFlow(int V) : V(V) { G.assign(V, vector<edge>()); }
  void add_edge(int from, int to, int cap) {
    G[from].push_back((edge){to, cap, (int)G[to].size()});
    G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
  }
  void bfs(int s) {
    level.assign(V, -1);
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto& e : G[v]) {
        if (e.cap > 0 and level[e.to] < 0) {
          level[e.to] = level[v] + 1;
          q.push(e.to);
        }
      }
    }
  }
  int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int& i = itr[v]; i < (int)G[v].size(); ++i) {
      edge& e = G[v][i];
      if (e.cap > 0 and level[v] < level[e.to]) {
        int d = dfs(e.to, t, min(f, e.cap));
        if (d > 0) {
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  int run(int s, int t) {
    int ret = 0, f;
    while (bfs(s), level[t] >= 0) {
      itr.assign(V, 0);
      while ((f = dfs(s, t, 10000)) > 0) ret += f;
    }
    return ret;
  }
};
struct PrimeFactor {
  vector<int> LowestPrimeFactor;
  vector<int> Prime;
  int N;
  PrimeFactor(int N0) : LowestPrimeFactor(N0 + 1) {
    N = N0;
    N++;
    LowestPrimeFactor.resize(N);
    for (int i = 1; i < N; i++) {
      LowestPrimeFactor[i] = i;
    }
    for (int i = 2; i < N; i++) {
      if (LowestPrimeFactor[i] == i) {
        Prime.push_back(i);
      }
      for (int j = 0; j < Prime.size(); j++) {
        if (Prime[j] * i < N && Prime[j] <= LowestPrimeFactor[i]) {
          LowestPrimeFactor[Prime[j] * i] = Prime[j];
        } else {
          break;
        }
      }
    }
  }
  vector<int> PrimeDivide(int X) {
    vector<int> ans;
    while (X != 1) {
      ans.push_back(LowestPrimeFactor[X]);
      X /= LowestPrimeFactor[X];
    }
    return ans;
  }
  vector<long long> PrimeDivide(long long X0) {
    vector<long long> ans;
    int X = (int)X0;
    int i = 0;
    while (X >= N) {
      if (X % Prime[i] == 0) {
        ans.push_back(Prime[i]);
        X /= Prime[i];
      } else {
        i++;
        if (i == Prime.size() || 1LL * Prime[i] * Prime[i] > X) {
          ans.push_back(X);
          X = 1;
        }
      }
    }
    while (X != 1) {
      ans.push_back(LowestPrimeFactor[X]);
      X /= LowestPrimeFactor[X];
    }
    return ans;
  }
  vector<int> Divisor(int X) {
    vector<int> ans;
    ans.push_back(1);
    while (X != 1) {
      int p = LowestPrimeFactor[X];
      int c = 0;
      while (X % p == 0) {
        X /= p;
        c++;
      }
      int l = ans.size();
      int d = p;
      for (int i = 1; i <= c; i++) {
        for (int j = 0; j < l; j++) {
          ans.push_back(d * ans[j]);
        }
        d *= p;
      }
    }
    return ans;
  }
  vector<long long> Divisor(long long X0) {
    vector<long long> ans;
    int X = (int)X0;
    ans.push_back(1);
    int i = 0;
    while (X >= N) {
      if (X % Prime[i] == 0) {
        int p = Prime[i];
        int c = 0;
        while (X % p == 0) {
          X /= p;
          c++;
        }
        int l = ans.size();
        int d = p;
        for (int k = 1; k <= c; k++) {
          for (int j = 0; j < l; j++) {
            ans.push_back(d * ans[j]);
          }
          d *= p;
        }
      } else {
        i++;
        if (i == Prime.size() || 1LL * Prime[i] * Prime[i] > X) {
          int l = ans.size();
          for (int j = 0; j < l; j++) {
            ans.push_back(X * ans[j]);
          }
          X = 1;
        }
      }
    }
    while (X != 1) {
      int p = LowestPrimeFactor[X];
      int c = 0;
      while (X % p == 0) {
        X /= p;
        c++;
      }
      int l = ans.size();
      int d = p;
      for (int k = 1; k <= c; k++) {
        for (int j = 0; j < l; j++) {
          ans.push_back(d * ans[j]);
        }
        d *= p;
      }
    }
    return ans;
  }
  int Phi(int X) {
    int ans = X;
    while (X != 1) {
      int p = LowestPrimeFactor[X];
      while (X % p == 0) {
        X /= p;
      }
      ans /= p;
      ans *= p - 1;
    }
    return ans;
  }
  long long Phi(long long X0) {
    int ans = (int)X0;
    int X = (int)X0;
    int i = 0;
    while (X >= N) {
      if (X % Prime[i] == 0) {
        int p = Prime[i];
        while (X % p == 0) {
          X /= p;
        }
        ans /= p;
        ans *= p - 1;
      } else {
        i++;
        if (i == Prime.size() || 1LL * Prime[i] * Prime[i] > X) {
          int p = X;
          ans /= p;
          ans *= p - 1;
          X = 1;
        }
      }
    }
    while (X != 1) {
      int p = LowestPrimeFactor[X];
      while (X % p == 0) {
        X /= p;
      }
      ans /= p;
      ans *= p - 1;
    }
    return ans;
  }
};
long long A[100];
pair<int, int> B[100];
void Calc() {
  int N = rei();
  int M = rei();
  for (int i = 0; i < N; i++) {
    A[i] = rei();
  }
  for (int i = 0; i < M; i++) {
    int x = rei() - 1;
    int y = rei() - 1;
    if (x & 1) {
      B[i] = {y, x};
    } else {
      B[i] = {x, y};
    }
  }
  set<long long> Prime;
  PrimeFactor PF(100000);
  for (int i = 1; i < N; i += 2) {
    vector<long long> PD = PF.PrimeDivide(A[i]);
    for (long long s : PD) {
      Prime.insert(s);
    }
  }
  int ans = 0;
  for (set<long long>::iterator it = Prime.begin(), end = Prime.end();
       it != end; ++it) {
    int P = *it;
    MaxFlow MF(N + 2);
    int S = N;
    int G = N + 1;
    for (int i = 0; i < N; i++) {
      int c = 0;
      while (A[i] % P == 0) {
        c++;
        A[i] /= P;
      }
      if (c) {
        if (i & 1) {
          MF.add_edge(i, G, c);
        } else {
          MF.add_edge(S, i, c);
        }
      }
    }
    for (int i = 0; i < M; i++) {
      MF.add_edge(B[i].first, B[i].second, 3000);
    }
    ans += MF.run(S, G);
  }
  cout << ans << endl;
}
int main(int argc, char** argv) {
  ios::sync_with_stdio(false), cin.tie(0);
  cout.tie(0);
  Calc();
  return 0;
}
