#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define f first
#define s second
#define pb push_back

typedef long long ll;
typedef pair<int, int> ii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const int MAXC = 1e5+10;
const int MAXV = 1e4+10;

bool tot[MAXC];
set<int> ans[MAXV];
vector<int> g[MAXV];
int c[MAXV];

bool vis[MAXV];

int gcd(int a, int b){
	if (b == 0) return a;
	return gcd(b, a%b);
}

void dfs(int v){
	vis[v] = true;
	for (int i : g[v]){
		if (vis[i]) continue;
		dfs(i);
		vector<int> inc;

		for (int j : ans[i])
			for (int k : ans[v])
				inc.push_back(gcd(gcd(j, k), c[v]));

		for (int j : inc)
			ans[v].insert(j);
	}
	for (int j : ans[v])
		tot[j] = true;
}

int main(){ _
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> c[i];
		ans[i].insert(c[i]);
	}
	while (m--){
		int l, r; cin >> l >> r;
		g[l].push_back(r);
		g[r].push_back(l);
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i]){
			dfs(i);
			cout << "!" << endl;
		}
	int pa = 0;
	for (int i : tot) pa += i;
	cout << pa << endl;
	exit(0);
}