// Slower C++ solution:
#include <iostream>

#include <vector>

#define inf 1000000000



using namespace std;



struct edge{

	int to, cap, rev;

	edge(int a, int b, int c){

		to = a, cap = b, rev = c;

	}

};



int V, S, T;

int m, n;

int b[505], r[505];

vector<edge> G[1005];

bool used[1005];



void addedge(int s, int t)

{

	G[s].push_back( edge(t, 1, G[t].size()) );

	G[t].push_back( edge(s, 0, G[s].size() - 1) );

}



int gcd(int a, int b)

{

	if(b == 0) return a;

	return gcd(b, a%b);

}



int dfs(int v, int t, int c)

{

	if(v == t) return c;

	used[v] = true;

	

	int ret;

	for(int i = 0; i < (int)G[v].size(); i++){

		if(used[G[v][i].to] || G[v][i].cap == 0) continue;

		ret = dfs(G[v][i].to, t, min(c, G[v][i].cap));

		if(ret > 0){

			G[v][i].cap -= ret;

			G[G[v][i].to][G[v][i].rev].cap += ret;

			return ret;

		}

	}

	return 0;

}



int main(void)

{

	while(1){

		cin >> m >> n;

		if(m == 0 && n == 0) break;

		V = m + n;

		S = 0, T = V+1;

		

		for(int i = 1; i <= m; i++) cin >> b[i];

		for(int i = 1; i <= n; i++) cin >> r[i];

		

		for(int i = 0; i <= T; i++) G[i].clear();

		for(int i = 1; i <= m; i++) addedge(S, i);

		for(int i = 1; i <= n; i++) addedge(m+i, T);

		

		for(int i = 1; i <= m; i++){

			for(int j = 1; j <= n; j++){

				if(gcd(b[i], r[j]) == 1) continue;

				addedge(i, m+j);

			}

		}

		

		int ret, ans = 0;

		while(1){

			for(int i = 0; i <= T; i++) used[i] = false;

			ret = dfs(S, T, inf);

			if(ret == 0) break;

			ans += ret;

		}

		

		cout << ans << endl;

	}

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2160513336637242x):
#include <iostream>

#include <string>

#include <vector>

#include <utility>

#include <queue>

#define llint long long

#define inf 1e18



using namespace std;

typedef pair<llint, llint> P;



struct edge{

	llint to, cap, rev;

	edge(llint a, llint b, llint c){

		to = a, cap = b, rev = c;

	}

};



llint m, n;

llint b[505], r[505];



vector<edge> G[1005];

llint S, T;

llint level[1005], iter[1005];



void bfs(llint s)

{

	for(int i = 1; i <= T; i++) level[i] = inf;

	level[s] = 0;

	

	queue<int> Q;

	Q.push(s);

	while(Q.size()){

		int v = Q.front();

		Q.pop();

		for(int i = 0; i < G[v].size(); i++){

			int u = G[v][i].to;

			if(G[v][i].cap <= 0 || level[u] < inf) continue;

			level[u] = level[v] + 1;

			Q.push(u);

		}

	}

}



llint dfs(int v, llint f)

{

	if(v == T) return f;

	

	llint ret;

	for(llint &i = iter[v]; i < G[v].size(); i++){

		if(level[v] >= level[G[v][i].to] || G[v][i].cap <= 0) continue;

		ret = dfs(G[v][i].to, min(f, G[v][i].cap));

		if(ret > 0){

			G[v][i].cap -= ret;

			G[G[v][i].to][G[v][i].rev].cap += ret;

			return ret;

		}

	}

	return 0;

}



void add_edge(int s, int t, llint cap)

{

	G[s].push_back(edge(t, cap, G[t].size()));

	G[t].push_back(edge(s, 0, G[s].size()-1));

}



llint gcd(llint a, llint b)

{

	if(b == 0) return a;

	return gcd(b, a%b);

}



int main(void)

{

	while(1){

		cin >> m >> n;

		if(n == 0 || m == 0) break;

		

		for(int i = 1; i <= m; i++) cin >> b[i];

		for(int i = 1; i <= n; i++) cin >> r[i];

		

		S = n+m+1, T = n+m+2;

		for(int i = 1; i <= T; i++) G[i].clear();

		for(int i = 1; i <= m; i++){

			for(int j = 1; j <= n; j++){

				if(gcd(b[i], r[j]) > 1) add_edge(i, m+j, 1);

			}

		}

		for(int i = 1; i <= m; i++) add_edge(S, i, 1);

		for(int i = 1; i <= n; i++) add_edge(m+i, T, 1);

		

		llint ans = 0, flow;

		while(1){

			bfs(S);

			if(level[T] >= inf) break;

			for(int i = 1; i <= T; i++) iter[i] = 0;

			while(1){

				flow = dfs(S, inf);

				if(flow <= 0) break;

				ans += flow;

			}

		}

		cout << ans << endl;

	}

	return 0;

}