#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long int
#define maxN 1000000000
#define rootN 31629
int A[105],X[105],Y[105],N;
int F[rootN],primecount=0;
int factor[100][rootN];
vector<int> prime;
void sieve()
{
int i,j;
for(i=2;i<rootN;i++)
if(F[i]==0) {
prime.pb(i); //i is a prime number
for(j=i+i;j<rootN;j+=i)
F[j]=1;
}
}
// 8 12 8 = 2 3 8
void factorise() {
int i,j;
for(i=1;i<=N;i++)
for(j=0;j<prime.size();j++)
while(A[i]%prime[j]==0) {
factor[i][j]++;
A[i]/=prime[j];
}
}
int min(int a,int b) {
if(a<b)
return a;
else
return b;
}
int main() {
prime.clear();
sieve();
int M,i,j;
cin>>N>>M;
ll ans=0;
for(i=1;i<=N;i++)
cin>>A[i];
factorise();
for(i=0;i<M;i++) {
cin>>X[i]>>Y[i];
for(j=0;j<prime.size();j++)
if(factor[X[i]][j]>0 && factor[Y[i]][j] >0){
ans+=min( factor[X[i]][j],factor[Y[i]][j] );
if( factor[X[i]][j] < factor[Y[i]][j] ) {
factor[Y[i]][j]-=factor[X[i]][j];
factor[X[i]][j]=0;
}
else {
factor[X[i]][j]-=factor[Y[i]][j];
factor[Y[i]][j]=0;
}
}
}
for(i=0;i<M;i++) {
if(A[X[i]]>1 && A[Y[i]]>1 ) {
if(A[X[i]]==A[Y[i]]) {
ans+=1;
A[X[i]]=1;
A[Y[i]]=1;
}
}
}
cout<<ans<<"\n";
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGxsIGxvbmcgbG9uZyBpbnQKCiNkZWZpbmUgbWF4TiAxMDAwMDAwMDAwCiNkZWZpbmUgcm9vdE4gMzE2MjkKCmludCBBWzEwNV0sWFsxMDVdLFlbMTA1XSxOOwppbnQgRltyb290Tl0scHJpbWVjb3VudD0wOwppbnQgZmFjdG9yWzEwMF1bcm9vdE5dOwp2ZWN0b3I8aW50PiBwcmltZTsKCnZvaWQgc2lldmUoKQp7CmludCBpLGo7CmZvcihpPTI7aTxyb290TjtpKyspCmlmKEZbaV09PTApIHsKcHJpbWUucGIoaSk7CS8vaSBpcyBhIHByaW1lIG51bWJlcgpmb3Ioaj1pK2k7ajxyb290TjtqKz1pKQpGW2pdPTE7Cn0KCn0KCi8vIDggMTIgOCA9IDIgMyA4Cgp2b2lkIGZhY3RvcmlzZSgpIHsKaW50IGksajsKZm9yKGk9MTtpPD1OO2krKykKZm9yKGo9MDtqPHByaW1lLnNpemUoKTtqKyspIAp3aGlsZShBW2ldJXByaW1lW2pdPT0wKSB7CmZhY3RvcltpXVtqXSsrOwpBW2ldLz1wcmltZVtqXTsKfQoKfQoKaW50IG1pbihpbnQgYSxpbnQgYikgewppZihhPGIpCnJldHVybiBhOwplbHNlCnJldHVybiBiOwp9CgppbnQgbWFpbigpIHsKCnByaW1lLmNsZWFyKCk7CnNpZXZlKCk7CgppbnQgTSxpLGo7CmNpbj4+Tj4+TTsKCmxsIGFucz0wOwoKZm9yKGk9MTtpPD1OO2krKykgCmNpbj4+QVtpXTsKCmZhY3RvcmlzZSgpOwoKZm9yKGk9MDtpPE07aSsrKSB7CmNpbj4+WFtpXT4+WVtpXTsKCglmb3Ioaj0wO2o8cHJpbWUuc2l6ZSgpO2orKykgCglpZihmYWN0b3JbWFtpXV1bal0+MCAmJiBmYWN0b3JbWVtpXV1bal0gPjApewoKCWFucys9bWluKCBmYWN0b3JbWFtpXV1bal0sZmFjdG9yW1lbaV1dW2pdICApOwoKCWlmKCBmYWN0b3JbWFtpXV1bal0gPCBmYWN0b3JbWVtpXV1bal0gKSB7CglmYWN0b3JbWVtpXV1bal0tPWZhY3RvcltYW2ldXVtqXTsKCWZhY3RvcltYW2ldXVtqXT0wOwoJfQoJZWxzZSB7CglmYWN0b3JbWFtpXV1bal0tPWZhY3RvcltZW2ldXVtqXTsKCWZhY3RvcltZW2ldXVtqXT0wOwoJfQoKCX0KCn0KCgoKZm9yKGk9MDtpPE07aSsrKSB7CmlmKEFbWFtpXV0+MSAmJiBBW1lbaV1dPjEgKSB7CmlmKEFbWFtpXV09PUFbWVtpXV0pIHsKYW5zKz0xOwpBW1hbaV1dPTE7CkFbWVtpXV09MTsKfQp9Cn0KCmNvdXQ8PGFuczw8IlxuIjsKCnJldHVybiAwOwp9