#include<iostream>

using namespace std;
int n,m;
bool V[1000];
bool C[1000][1000];
int P[1000];

int gcd(int a,int b);
bool match(int a);

int main(){


  while(cin >> n >> m && (n>0 || m>0) ){
    int blue[n],red[m];
    
    for(int i=0;i<n;i++){
      cin >> blue[i];
    }
    for(int i=0;i<m;i++){
      cin >> red[i];
      P[i]=-1;
      V[i]=false;
    }

    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
	if(gcd(blue[i],red[j])>1)C[i][j]=1;
	else C[i][j]=0;
      }
    }
    int ans=0;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++)V[j]=false;
      if(match(i)) ans++;
    }
    
    cout << ans << endl;
  }
}

int gcd(int a,int b){
  if(a<b){
    int temp=b;
    b=a;
    a=temp;
  }

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

bool match(int a){
   if(a<0)return true;

   for(int j=0;j<m;j++){
     if(!C[a][j] || V[j] )continue;
     V[j]=true;
     if(match(P[j])){
       P[j]=a;
       return true;
     }
   }
   return false;
 }

   