#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 105

using namespace std;
int a[nmax],N,m,l[nmax],r[nmax];
int ci[nmax*nmax],p,g,cj[nmax*nmax];
int st[nmax*nmax],dr[nmax*nmax],sol;
bool viz[nmax];
struct Cord{
 int x,y;
}d[nmax],A[nmax],B[nmax];
vector<int>G[nmax*nmax];

inline void Fact(int x){
    x = a[x];
    int i,k=x,j;
    A[0].x = 0;

    for(i = 2; i*i <= k; ++i)
        if(x%i==0){

            while(x > 1&&x%i==0)
               A[++A[0].x].x = i,x/=i,A[A[0].x].y = ++p,ci[p] = i;
    }
   for(i = 1; i <= A[0].x;++i)
    for(j = 1; j <= B[0].x; ++j)
      G[A[i].y].push_back(B[j].y);


}
inline void First(int y){
    int k,i;
    y = a[y];
  k = y;
  B[0].x = 0;

    for(i = 2; i*i <= k; ++i)
        if(y%i==0){
            while(y > 1&&y%i==0)
               B[++B[0].x].x = i,y/=i,B[B[0].x].y = ++g,cj[g] = i;
    }
    k = y;
    if(k>1)B[++B[0].x].x=k,B[B[0].x].y=++g,cj[g]=k;
//
//    for(i = 1; i <= B[0].x;++i)
//        cout << B[i].x <<' ';
}
inline bool cmp(const Cord &A,const Cord &B){
 return A.y < B.y;
}
inline void Prec(){
 int i,x,y,j,k,q;
  for(i = 1; i <= m; ++i){
    if(!(l[i]&1)) swap(l[i],r[i]);
    d[i].x = l[i];
    d[i].y = r[i];
  }
    sort(d+1,d+m+1,cmp);
  for(i = 1; i <= m; ++i){
      x = l[i];
      y = r[i];
      j = i+1;
      k = y;
      while(d[j].y == k)++j;
      First(k);
   for(q = i; q < j; ++q){
     Fact(l[q]);
   }
        i = j - 1;
  }
}
inline bool Cuplaj(int nod){
    for(vector<int>::iterator it = G[nod].size();it!=G[])
}
inline void solve(){
 int gata = 1,i;
 while(gata){
    gata = 0;
    for(i = 1;i <= p; ++i)
        if(!st[i] && Cuplaj(i)) gata = 1,++sol;
 }
}
int main(){
    int i,x,y;
    ifstream fin("txt.in");
    fin >> N >> m;
    for(i = 1; i <= N; ++i)
        fin >> a[i];
    for(i = 1; i <= m; ++i){
        fin >> l[i] >> r[i];
    }
    fin.close();
    ios::sync_with_stdio(false);
    Prec();
    return 0;
}