#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<functional>
#include<cstdio>
#define rep(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define MaxCards 1000
using namespace std;
int	b, r, V;
int blue[MaxCards], red[MaxCards];
vector<int> G[MaxCards];
int match[MaxCards]; // マッチングのペア
bool used[MaxCards]; // DFSですでに調べたかのフラグ


// uからvを結ぶ辺をグラフに追加する
void add_edge(int u, int v) {
	G[u].push_back(v);
	G[v].push_back(u);
}

// 増加パスをDFSで探す
bool dfs(int v) {
	used[v] = true;
	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 true;
		}
	}
	return false;
}

// 二部グラフの最大マッチングを求める
int bipartite_matching() {
	int res = 0;
	memset(match, -1, sizeof(match));
	for (int v = 0; v < V; v++) {
		if (match[v] < 0) {
			memset(used, 0, sizeof(used));
			if (dfs(v)) {
				res++;
			}
		}
	}
	return res;
}
int gcd(int n1, int n2){
	if (n1%n2 == 0) return n2;
	return gcd(n2, n1%n2);
}
int main(){
	while (true){
		memset(blue, 0, sizeof(blue));
		memset(red, 0, sizeof(red));
		for (int i = 0; i<MaxCards; i++){
			G[i].clear();
		}
		cin >> b >> r;
		V = b + r;
		if (b == 0)
			break;
		int idx = 0;
		for (int i = 0; i<b; i++){
			cin >> blue[i];
		}
		for (int i = 0; i<r; i++){
			cin >> red[i];
		}
		for (int i = 0; i<b; i++){
			for (int j = 0; j<r; j++){
				if (blue[i]>red[j]){
					if (gcd(blue[i], red[j]) != 1){
						add_edge(i, b + j);
					}
				}
				else if (gcd(red[j], blue[i]) != 1){
					add_edge(i, b + j);
				}
			}
		}
		cout << bipartite_matching() << endl;
	}
	return 0;
}