// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <numeric>

#include <map>

#define REP(i,n) for (int i=0;i<(n);i++)



using namespace std;



const int INF = 1e9;

const int MAX_V = 1010;

struct edge{ int to,cap,rev;edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){}};



vector<vector<edge> > G(MAX_V); //??°???????????£??\???????????¨???

bool used[MAX_V]; //DFS??§??¢???????????????????????????????????°



void init(int n){

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

}



void add_edge(int from, int to, int cap){

	G[from].push_back(edge(to,cap,G[to].size()));

	G[to].push_back(edge(from,0,G[from].size() - 1));

}



int dfs(int v, int t, int f){

	if(v == t) return f;

	used[v] = true;

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

		edge &e = G[v][i];

		if( !used[e.to] && e.cap > 0){

			int d = dfs(e.to,t,min(f,e.cap));

			if(d > 0){

				e.cap -=d;

				G[e.to][e.rev].cap += d;

				return d;

			}

		}

	}

	return 0;

}



int max_flow(int s, int t){

	int flow = 0;

	for(;;){

		fill(used,used + MAX_V,false);

		int f = dfs(s,t,INF);

		if(f == 0)return flow;

		flow += f;

	}

}





int main(){

  cin.tie(0);

  ios::sync_with_stdio(false);

	int m,n;

	while(cin >> m >> n,m){

		int s = m + n,t = s + 1;

		init(t);

		vector<int> b(m),r(n);

		REP(i,m){

			cin >> b[i];

			add_edge(s,i,1);//????????§????§??????????????????¶

		}

		REP(i,n){

			cin >> r[i];

			add_edge(i + m,t,1);//????????§???????????????????????¶

		}

		REP(i,m){

			REP(j,n){

				if(__gcd(b[i],r[j]) != 1){

					add_edge(i,j + m,1);

				}

			}

		}

		cout << max_flow(s,t) << endl;

	}

  return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <numeric>

#include <map>

#define REP(i,n) for (int i=0;i<(n);i++)



using namespace std;



const int MAX_V = 1010;

vector<vector<int> > G(MAX_V); //??°???????????£??\???????????¨???

bool used[MAX_V]; //DFS??§??¢???????????????????????????????????°

int match[MAX_V]; //??????????????°????????¢



void init(int n){

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

}



void add_edge(int from, int to){

	G[from].push_back(to);

	G[to].push_back(from);

}



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 V){

	int res = 0;

	fill(match, match + V,-1);

	for(int v = 0;v < V;v++){

		if(match[v] < 0){

			fill(used, used + V, false);

			if(dfs(v))res++;

		}

	}

	/*

	//??????????????????

	REP(i,V){

		if(match[i] >= 0) cout << i << ' ' << match[i] << endl;

		}*/

	return res;

}





int main(){

  cin.tie(0);

  ios::sync_with_stdio(false);

	int m,n;

	while(cin >> m >> n,m){

		//		int s = m + n,t = s + 1;

		init(m+n);

		vector<int> b(m),r(n);

		REP(i,m){

			cin >> b[i];

			//			add_edge(s,i);//????????§????§??????????????????¶

		}

		REP(i,n){

			cin >> r[i];

			//			add_edge(i + m,t);//????????§???????????????????????¶

		}

		REP(i,m){

			REP(j,n){

				if(__gcd(b[i],r[j]) != 1){

					add_edge(i,j + m);

				}

			}

		}

		cout << bipartite_matching(m+n) << endl;

	}

  return 0;

}

// Fastest known solution for this problem: