#include<stdio.h>
#include<string.h>

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int n,m;
int b[500],r[500];
int flow[500][500];
int sink[500];

int visitb[500];
int visitr[500];
int blue(int i){
	int j;
	if(visitb[i]==1)return 0;
	visitb[i]=1;
	for(j=0;j<n;j++){
		if(flow[i][j]==0 && red(j)==1){
			flow[i][j] = 1;
			return 1;
		}
	}
	return 0;
}
int red(int j){
	int i;
	if(visitr[j]==1)return 0;
	visitr[j]=1;
	if(sink[j]==0){
		sink[j]=1;
		return 1;
	}
	for(i=0;i<n;i++){
		if(flow[i][j]==1 && blue(i)==1){
			flow[i][j] = 0;
			return 1;
		}
	}
	return 0;
}
int main(){
	int i,j;
	int res;
	while(scanf("%d%d",&m,&n)==2&&(m|n)){
		for(i=0;i<m;i++)scanf("%d",&b[i]);
		for(i=0;i<n;i++)scanf("%d",&r[i]);
		memset(flow,0,sizeof(flow));
		memset(sink,0,sizeof(sink));
		for(i=0;i<m;i++){
			for(j=0;j<n;j++){
				if(1==gcd(b[i],r[j])){
					flow[i][j] = -1;
				}
			}
		}
		res=0;
		for(i=0;i<m;i++){
			memset(visitb,0,sizeof(visitb));
			memset(visitr,0,sizeof(visitr));
			res += blue(i);
		}
		printf("%d\n",res);
	}
}