#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

/*
ACMプログラミング・コンテスト 国内予選 2009 Problem E カードゲーム

問題は、青、赤のカードセットから1枚ずつを取り出し、2以上の共通の約数がある場合にペアとしてカードセットから取り出し、
最も多くのペアを作成する組み合わせを見つけることである。全探索ですべてのカードの組み合わせについて調べる方法の場合、
実時間で計算を終了することができない。そこで、最もペアになる可能性のないものから順にペアを作成する方法をとった。
また、計算時間を短くするために、何度も割り算をしないようにまず素数を数多く作成しておく。ただし、カードの取りうる値以下の
すべての素数を配列に保存することができなかったため、できるだけ多くの素数を保存し、それを超える場合には、奇数の数字で
1つづつ割れるかどうかをチェックするようにしている。
*/

// 予め作成しておく素数の数
#define	SOSU_COUNT 190000

// ペアになる可能性のあるカードが残っているかどうかを確認する。
// 1つもペアになる可能性がない場合、1を返す。
// まだ、ペアになる可能がある場合、0を返す。
int finished(char relations[][500],int m,int n)
{
	for(int bcnt=0;bcnt<m;bcnt++){
		for(int rcnt=0;rcnt<n;rcnt++){
			if(relations[bcnt][rcnt]==1){
				return 0;
			}
		}
	}
	return 1;
}
// 第一引数の数字が、第二引数にある数字のどれかで割れるかどうかを確認する。
int isDivided(int value,int a_sosu[],int a_sosu_count)
{
	for(int cnt=0;cnt<a_sosu_count;cnt++){
		if(value % a_sosu[cnt] == 0){
			return 1;
		}
	}
	return 0;
}
// 第一引数を割ることのできる数字列を、与えられた素数列の中から抽出する。
// 与えられた素数列を超える数値については、奇数の数字をすべてチェックし、
// 第一引数を割ることのできる数は、発見した割ることのできる数字列に追加する。
int findASosu(int value,int sosu[],int sosu_count,int* a_sosu_count,int a_sosu[],int max_a_sosu_count)
{
	for(int cnt=0;cnt<sosu_count && sosu[cnt]<=value;cnt++){
		if(value%sosu[cnt]==0){
			a_sosu[*a_sosu_count] = sosu[cnt];
			(*a_sosu_count)++;
			if(*a_sosu_count == max_a_sosu_count){
				printf("+++++++++++++++++++++\n");
				printf("+++++++++++++++++++++\n");
				printf("+++++++++++++++++++++\n");
				return max_a_sosu_count;
			}
		}
	}
	for(int cnt=sosu[sosu_count-1]+2;cnt<=value;cnt+=2){
		if(value%cnt==0){
			a_sosu[*a_sosu_count] = cnt;
			(*a_sosu_count)++;
			if(*a_sosu_count == max_a_sosu_count){
				printf("+++++++++++++++++++++\n");
				printf("+++++++++++++++++++++\n");
				printf("+++++++++++++++++++++\n");
				return max_a_sosu_count;
			}
		}
	}
	return *a_sosu_count;
}
// 素数かどうかをチェックする。すでにその数字までに見つけられた
// 素数で割れるかどうかによってチェックする。
int isSosu(int value,int sosu[])
{
	int cnt=0;
	for(;sosu[cnt]!=0 && sosu[cnt]<(value/2);cnt++){
		if(value%sosu[cnt]==0){
			return 0;
		}
	}
	for(;sosu[cnt]!=0;cnt++);
	sosu[cnt] = value;
	return cnt;
}
// ペアになることのできるカード数を取得する。
// typeは、1の場合は、青カードから赤カードを
// 2の場合は、逆の可能性を調べる。
int countFits(int type,char relations[][500],int index,int loop)
{
	int count = 0;
	for(int cnt=0;cnt<loop;cnt++){
		count += (int)relations[type==1?index:cnt][type==1?cnt:index];
	}
	return count;
}
// ペアになることのできる可能性をすべて消す。
// typeは、1の場合は、青カードから赤カードを
// 2の場合は、逆の可能性をすべて消す。
int remove(int type,char relations[][500],int index,int loop,int t_loop)
{
	int t_index = -1;
	for(int cnt=0;cnt<loop;cnt++){
		if(t_loop!=0 && relations[type==1?index:cnt][type==1?cnt:index]==1){
			t_index = cnt;
		}
		relations[type==1?index:cnt][type==1?cnt:index] = 0;
	}
	return t_index;
}
// デバック用の関数：ペアになれる情報を出力する。
void printRelations(char relations[][500],int m,int n)
{
	for(int bcnt=0;bcnt<m;bcnt++){
		for(int rcnt=0;rcnt<n;rcnt++){
			printf("%d",relations[bcnt][rcnt]);
		}
		printf("\n");
	}
}
int main()
{
	int sosu[SOSU_COUNT];
	for(int cnt=0;cnt<SOSU_COUNT;cnt++){
		sosu[cnt] = 0;
	}
	sosu[0] = 2;
	for(int cnt=3;(SOSU_COUNT-1)!=isSosu(cnt,sosu);cnt+=2);

	int m,n;
	while(scanf("%d %d",&m,&n) && (m!=0 && n!=0)){
//printf("m,n = %d,%d\n",m,n);

		int b[500],r[500];
		for(int mcnt=0; mcnt<m; mcnt++){
			scanf("%d",&b[mcnt]);
		}
		for(int ncnt=0; ncnt<n; ncnt++){
			scanf("%d",&r[ncnt]);
		}
		char relations[500][500];
		for(int bcnt=0;bcnt<m;bcnt++){
//printf("bcnt = %d\n",bcnt);
			int a_sosu_count = 0;
			int a_sosu[1024];
			findASosu(b[bcnt],sosu,SOSU_COUNT,&a_sosu_count,a_sosu,1024);
			for(int rcnt=0;rcnt<n;rcnt++){
				relations[bcnt][rcnt] = isDivided(r[rcnt],a_sosu,a_sosu_count);
//printf("b[bcnt]=%d,r[rcnt]=%d,relations %d\n",b[bcnt],r[rcnt],relations[bcnt][rcnt]);
			}
		}
//printRelations(relations,m,n);
		int pair = 0;
		while(0 == finished(relations,m,n)){
			int min_count = m>n?(m+1):(n+1);
			int min_count_index = -1;
			int min_count_type = -1;

			for(int type=1;type<=2;type++){
				int loop = type==1?m:n;
				int t_loop = type==1?n:m;
				for(int cnt=0;cnt<loop;cnt++){
					int count = countFits(type,relations,cnt,t_loop);
//printf("type=%d,cnt=%d,t_loop=%d,count=%d\n",type,cnt,t_loop,count);
					if(count!=0 && (min_count_index==-1||min_count>count)){
						min_count = count;
						min_count_index = cnt;
						min_count_type = type;
					}
					if(min_count == 1){
						break;
					}
				}
			}
//printf("min_count=%d, min_count_index=%d, min_count_type=%d\n",min_count,min_count_index,min_count_type);
			int t_index = remove(min_count_type,relations,min_count_index,min_count_type==1?n:m,min_count_type==1?m:n);
//printf("t_index=%d\n",t_index);
			if(t_index != -1){
				remove(min_count_type==1?2:1,relations,t_index,min_count_type==1?m:n,0);
				pair++;
			}
//printRelations(relations,m,n);
		}
		printf("%d\n",pair);
	}
//	printf("finished\n");
//	getch();
	return 0;
}