#include <iostream>
#include <vector>
#include <cstring>
#define SIZE 1000

using namespace std;

int m, n, b[501], r[501];
int match[SIZE];
bool used[SIZE];
vector<int> G[SIZE];

bool dfs(int v){
	used[v]=1;
	for(int i=0; i<G[v].size(); i++){
		int u=G[v][i], w=match[u];
		if(w<0||!used[w]&&dfs(w)){
			match[v]=u, match[u]=v;
			return 1;
		}
	}
	return 0;
}

void solve(){
	int res=0;
	memset(match, -1, sizeof(match));
	for(int v=0; v<m+n; v++){
		if(match[v]<0){
			memset(used, 0, sizeof(used));
			if(dfs(v)) res++;
		}
	}
	cout<<res<<endl;
}

int main(){
	while(1){
		cin >> n >> m;
		if(!n && !m) break;
		for(int i=0; i<n; i++){
			cin >> b[i];
		}
		for(int i=0; i<m; i++){
			cin >> r[i];
		}
		for(int i=0; i<SIZE; i++) G[i].clear();
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				int a=b[i], c=r[j];
				while(c){
					a%=c;
					swap(a, c);
				}
				if(a!=1)G[i].push_back(j+n), G[n+j].push_back(i);
			}
		}
		solve();
	}
}
