Cards (AOJ 1163) by letter
Contest: 3575    RunID: 2376092    Status: Accepted    Date: Sat Jun 17 15:18:25 JST 2017


#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
 
typedef long long ll;
typedef pair<int, int> ii;

#define DEBUG false

#define MAX_V 1100

int V;
vector<vector<int>> G(1100);
int match[MAX_V];
bool used[MAX_V];

bool dfs(int v){
	used[v] = true;
	rep(i, G[v].size()){
		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;
}

ll solve(){
	ll ret = 0;
	memset(match, -1, sizeof(match));
	rep(v, V){
		if(match[v] < 0){
			memset(used, 0, sizeof(used));
			if(dfs(v)) ret++;
		}
	}
	return ret;
}

int main(){

	ll n, m;
	/*
	vector<int> prime;
	vector<bool> used(10000001);
	REP(i, 2, 10000001){
		if(!used[i]) prime.push_back(i);
		for(int j = 2; i * j < 10000001; j++) used[i*j] = true;
	}
	*/
	
	while(cin >> n >> m){
		if(n == 0 && m == 0) break;
		
		rep(i, MAX_V) G[i].clear();
		V = n + m;
		vector<ll> b(n), r(m);
		rep(i, n) cin >> b[i];
		rep(i, m) cin >> r[i];
		
		rep(i, n){
			rep(j, m){
				if(__gcd(b[i], r[j]) != 1){
						G[i].push_back(n+j);
						G[n+j].push_back(i);
				}
			}
		}
	
		cout << solve() << endl;
	
		
	}
	
	return 0;
}