#include<stdio.h>
int n,m,f[1010];
int ff(int a,int b){
  if(a<b){
    if(a)return ff(a,b%a);
    return b;
  }
  if(b)return ff(b,a%b);
  return a;
}
int g(int s,int t,char d[1010][1010]){
  if(s==t)return 1;
  int i;
  for(i=0;i<n+m+2;i++){
    if(f[i]||d[s][i]==0)continue;
    f[i]=1;
    if(g(i,t,d)){
      d[s][i]=0;
      d[i][s]=1;
      return 1;
    }
  }
  return 0;
}
int main(){
  int i,j,a[510],b;
  while(scanf("%d %d",&n,&m),n||m){
    char d[1010][1010]={0};
    for(i=0;i<n;i++){
      scanf("%d",&a[i]);
      d[0][i+1]=1;
    }
    for(j=0;j<m;j++){
      scanf("%d",&b);
      for(i=0;i<n;i++){
	if(ff(a[i],b)-1)d[i+1][n+j+1]=1;
      }
      d[n+j+1][n+m+1]=1;
    }
    for(i=0;i<n+m+2;i++)f[i]=0;
    for(b=0;g(0,n+m+1,d);b++){
      for(i=0;i<n+m+2;i++)f[i]=0;
    }
    printf("%d\n",b);
  }
  return 0;
}