#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
	typedef struct edge{
	int to,cap,rev;
	}edge;
void add_edge(int from,int to,int cap,vector<vector<edge> > &g){
	edge f,t;
	f = (edge){to,cap,(int)g[to].size()};
	g[from].push_back(f);
	t = (edge){from,0,(int)g[from].size()-1};
	g[to].push_back(t);
}
int dfs(int v,int t,int f,vector<vector<edge> > &g,vector<bool> &used){
	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),g,used);
			if(d>0){
				e.cap -=d;
				g[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t,vector<vector<edge> > &g){
	int flow=0;
	while(1){
		vector<bool>  used(g.size(),false);
		int f = dfs(s,t,INF,g,used);
		if(f==0) return flow;
		flow+=f;
	}
}

int gcd(int a,int b){
if(b==0)return a;
else return gcd(b,a%b);
}
int main(){
	while(1){
	int n,m;
	cin>>m>>n;
	if(m==0)break;
	vector<int> b(m),r(n);
	for(int i=0;i<m;i++)cin>>b[i];
	for(int i=0;i<n;i++)cin>>r[i];
	vector<vector<edge> > g(n+m+2);
	for(int i=0;i<m;i++) add_edge(0,i+1,1,g);
	for(int i=0;i<n;i++) add_edge(m+i+1,m+n+1,1,g);
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(gcd(b[i],r[j])!=1)add_edge(i+1,1+m+j,1,g);
		}
	}
	cout<<max_flow(0,m+n+1,g)<<endl;
	}
	return 0;
}

