#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define INF 1e9
#define rep(i,n) for(int i=0;i<n;i++)

struct edge{int to,cap,rev;};

vector<edge> g[1002];
bool used[1002];

void addEdge(int from,int to,int cap){
	edge e;
	e.to=to;e.cap=cap;e.rev=g[to].size();
	g[from].push_back(e);
	e.to=from;e.cap=0;e.rev=g[from].size()-1;
	g[to].push_back(e);
}

int dfs(int v,int t,int f){
	if(v==t)return f;
	used[v]=1;
	rep(i,g[v].size()){
		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 maxFlow(int s,int t){
	int flow=0;
	for(;;){
		fill(used,used+1001,0);
		int f=dfs(s,t,INF);
		if(!f)return flow;
		flow+=f;
	}
}

int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}

int m,n,k,a[1002];

int main(){
	while(cin>>m>>n&&m){
		rep(i,m+n+2)g[i].clear();
		rep(i,m+n)cin>>a[i];
		int S=m+n,G=S+1;
		rep(i,m)addEdge(S,i,1);
		rep(i,n)addEdge(m+i,G,1);
		rep(i,m)rep(j,n)if(gcd(a[i],a[m+j])>1){addEdge(i,m+j,1);}
		cout<<maxFlow(S,G)<<endl;
	}
}