#include<cstdio>

using namespace std;

bool coprime(int a,int b){
	for(int t;b;t=a,a=b,b=t)	a%=b;
	return a==1;
}

int capa[1002][1002],flow[1002][1002],src,snk,sz;

bool findAugPath(int u,int *path,int &len,bool *visited,int i=0){
//if(i>10){puts("error");return false;}
//for(int j=0;j<i;j++)putchar(' ');printf("%d\n",u);
	path[i]=u;
	visited[u]=true;
	if(u==snk){ len=i+1; return true; }
	for(int v=0;v<sz;v++){
		if(!visited[v] && capa[u][v]-flow[u][v]>0){
//			visited[v]=true;
			bool b=findAugPath(v,path,len,visited,i+1);
//			visited[v]=false;
			if(b)	return true;
		}
	}
	return false;
}

int main(){
	for(int m,n;scanf("%d%d",&m,&n),m;){
		static int blue[500],red[500];
		for(int i=0;i<m;i++)	scanf("%d",blue+i);
		for(int j=0;j<n;j++)	scanf("%d",red+j);

		src=0,snk=m+n+1,sz=m+n+2;
		for(int i=0;i<sz;i++)for(int j=0;j<sz;j++){
			capa[i][j]=0;
			flow[i][j]=0;
		}

		for(int i=0;i<m;i++)	capa[src][1+i]=1;
		for(int i=0;i<m;i++)for(int j=0;j<n;j++){
			if(!coprime(blue[i],red[j]))	capa[1+i][1+m+j]=1;
		}
		for(int j=0;j<n;j++)	capa[1+m+j][snk]=1;

//for(int i=0;i<sz;i++){for(int j=0;j<sz;j++)printf("%2d ",capa[i][j]);puts("");}puts("");
		static int path[1002],len;
		static bool visited[1002];
		while(1){
			for(int u=0;u<sz;u++)	visited[u]=false;
			if(!findAugPath(src,path,len,visited))	break;
			for(int i=1,u=path[0];i<len;i++){
				int v=path[i];
				flow[u][v]++;
				flow[v][u]--;
				u=v;
			}
//for(int i=0;i<sz;i++){for(int j=0;j<sz;j++)printf("%2d",flow[i][j]);puts("");}puts("");
		}

		int maxmatch=0;
		for(int i=0;i<m;i++)for(int j=0;j<n;j++){
			if(flow[1+i][1+m+j]==1)	maxmatch++;
		}
		printf("%d\n",maxmatch);
	}

	return 0;
}