// 2009国内予選E カードゲーム
#include <iostream>
#include <vector>

using namespace std;

typedef vector< vector<int> > graph;

graph g;
vector<int> match;
vector<bool> visit;

bool search(int u){
	if(u<0) return true;
	for(int i=0;i<g[u].size();i++){
		int next = g[u][i];
		if(visit[next]) continue;
		visit[next] = true;
		if(search(match[next])){
			match[u] = next, match[next] = u;
			return true;
		}
	}
	return false;
}

int maximumMatch(int L, int R){
	int res = 0;
	match.assign(L+R, -1);
	for(int i=0;i<L;i++){
		visit.assign(L+R, false);
		res += search(i);
	}
	return res;
}

int gcd(int a, int b){ return b==0 ? a : gcd(b, a%b); }

int main(){
	int m, n;
	int blue[500], red[500];
	while(cin >> m >> n){
		if(!(m||n)) break;
		for(int i=0;i<m;i++) cin >> blue[i];
		for(int i=0;i<n;i++) cin >> red[i];
		g.assign(m+n, vector<int>());
		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++)
				if(gcd(blue[i],red[j])!=1){
					g[i].push_back(j+m);
					g[j+m].push_back(i);
				}
		cout << maximumMatch(m,n) << endl;
	}
}