#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct s {
	int dst, rev, cap;
	s(){}
	s(int d, int r, int c){
		dst=d; rev=r; cap=c;
	}
};

void add(int src, int dst, int cost, vector<vector<s> >& G) {
	G[src].push_back(s(dst,G[dst].size(),cost));
	G[dst].push_back(s(src,G[src].size()-1,0));
}

int dfs(int n, int dst, int flow, vector<vector<s> > &G, bool* vis) {
	if(vis[n]) return 0;
	if(n == dst) {
		return flow;
	}
	vis[n] = true;
	for(int i = 0; i < G[n].size(); i++) {
		if(G[n][i].cap > 0) {
			int res = dfs(G[n][i].dst, dst, min(flow,G[n][i].cap), G, vis);
			if(res) {
				G[n][i].cap -= res;
				G[G[n][i].dst][G[n][i].rev].cap += res;
				return res;
			}
		}
	}
	return 0;
}

int maxf(int src, int dst, vector<vector<s> > &G) {
	int res = 0;
	bool f = true;
	while(f) {
		f = false;
		bool vis[1100] = {};
		int tmp = dfs(src, dst, 100, G, vis);
		if(tmp) {
			f = true;
			res += tmp;
		}
	}
	return res;
}

int main() {
	int m, n;
	while(cin >> m >> n, m || n) {
		vector<int> b(m), r(n);
		vector<vector<s> > G(m+n+2);
		for(int i = 0; i < m; i++) cin >> b[i];
		for(int i = 0; i < n; i++) cin >> r[i];

		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				if(gcd(b[i],r[j]) > 1) {
					add(i+1, j+m+1, 1, G);
				}
			}
		}
		for(int i = 0; i < m; i++) add(0,i+1,1,G);
		for(int i = 0; i < n; i++) add(i+1+m,n+m+1,1,G);
		cout << maxf(0,n+m+1,G) << endl;
	}
}