#include <bits/stdc++.h>   using namespace std;   const long long INF = 1e15;   const int MOD = 1e9 + 7;   const double EPS = 1e-9;   const double PI = acos(-1.0);   mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());   const int N = 105;   pair<long long, long long> e[N];   long long n, m, a[N];   vector<vector<int>> capacity;   vector<vector<int>> adj;   int bfs(int s, int t, vector<int>& parent) {     fill(parent.begin(), parent.end(), -1);     parent[s] = -2;     queue<pair<int, int>> q;     q.push({s, MOD});     while (!q.empty()) {       int cur = q.front().first;       int flow = q.front().second;       q.pop();       for (int next : adj[cur]) {         if (parent[next] == -1 && capacity[cur][next]) {           parent[next] = cur;           int new_flow = min(flow, capacity[cur][next]);           if (next == t) return new_flow;           q.push({next, new_flow});         }       }     }     return 0;   }   int maxflow(int s, int t) {     int flow = 0;     vector<int> parent(N);     int new_flow;     while (new_flow = bfs(s, t, parent)) {       flow += new_flow;       int cur = t;       while (cur != s) {         int prev = parent[cur];         capacity[prev][cur] -= new_flow;         capacity[cur][prev] += new_flow;         cur = prev;       }     }     return flow;   }   void add_primes(long long x, set<long long>& primes) {     for (int i = 2; i <= x / i; ++i) {       if (x % i == 0) {         primes.insert(i);         while (x % i == 0) x /= i;       }     }     if (x != 1) primes.insert(x);   }   long long cnt(long long x, long long p) {     long long ret = 0;     while (x && x % p == 0) {       ++ret;       x /= p;     }     return ret;   }   int main() {     ios::sync_with_stdio(false);     cin.tie(NULL), cout.tie(NULL);     cin >> n >> m;     adj = vector<vector<int>>(N);     capacity = vector<vector<int>>(N, vector<int>(N));     set<long long> primes;     for (int i = 1; i <= n; ++i) {       cin >> a[i];       add_primes(a[i], primes);     }     for (int i = 1; i <= n; ++i) {       if (i & 1) {         adj[0].push_back(i);         adj[i].push_back(0);       } else {         adj[n + 1].push_back(i);         adj[i].push_back(n + 1);       }     }     for (int i = 0; i < m; ++i) {       cin >> e[i].first >> e[i].second;       int u = e[i].first;       int v = e[i].second;       adj[u].push_back(v);       adj[v].push_back(u);     }     long long ans = 0;     for (auto p : primes) {       for (int i = 1; i <= n; ++i) {         if (i & 1)           capacity[0][i] = cnt(a[i], p);         else           capacity[i][n + 1] = cnt(a[i], p);       }       for (int i = 0; i < m; ++i) {         int u = e[i].first;         int v = e[i].second;         if (u & 1)           capacity[u][v] = cnt(a[u], p);         else           capacity[v][u] = cnt(a[v], p);       }       ans += maxflow(0, n + 1);     }     cout << ans <<   n ;   }   