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