// Slower C++ solution:
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <climits>

#include <cmath>

#include <ctime>

#include <cassert>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <complex>

#include <string>

#include <vector>

#include <list>

#include <deque>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <bitset>

#include <iterator>

#include <functional>

#include <utility>

#include <algorithm>

#include <numeric>

#include <typeinfo>



using namespace std;



#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl

#define repi(i,a,b) for(int i=int(a);i<int(b);i++)

#define rep(i,n) repi(i,0,n)

#define iter(c) __typeof((c).begin())

#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)

#define allof(c) (c).begin(),(c).end()

#define mp make_pair



typedef unsigned int uint;

typedef long long ll;

typedef unsigned long long ull;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef vector<string> vs;

typedef pair<int,int> pii;



const int INFTY=1<<29;



struct Edge{

	int src,dst,weight;

	Edge(){}

	Edge(int src,int dst,int weight):src(src),dst(dst),weight(weight){}

};



typedef vector<Edge> Edges;

typedef vector<Edges> Graph;



bool DFS(Graph& g,int v,vi& used,vi& match)

{

	used[v]=true;

	rep(i,g[v].size()){

		int u=g[v][i].dst,w=match[u];

		if(w==-1 || !used[w] && DFS(g,w,used,match)){

			match[v]=u;

			match[u]=v;

			return true;

		}

	}

	return false;

}



int BiparateMatching(const Graph& _g,int m)

{

	int n=_g.size()-m;

	Graph g=_g;

	rep(i,_g.size())

		foreach(e,_g[i])

			g[e->dst].push_back(Edge(e->dst,e->src,e->weight));

	

	vi used(m+n);

	vi match(m+n,-1);

	int res=0;

	rep(i,m+n){

		if(match[i]==-1){

			fill(allof(used),0);

			res+=DFS(g,i,used,match);

		}

	}

	

	return res;

}



int main()

{

	for(int m,n;cin>>m>>n,m|n;){

		vi bs(m),rs(n);

		rep(i,m) cin>>bs[i];

		rep(i,n) cin>>rs[i];

		Graph g(m+n);

		rep(i,m) rep(j,n)

			if(__gcd(bs[i],rs[j])>1)

				g[i].push_back(Edge(i,m+j,1));

		cout<<BiparateMatching(g,m)<<endl;

	}

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2896907035047875x):
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <climits>

#include <cassert>

#include <iostream>

#include <iomanip>

#include <sstream>

#include <algorithm>

#include <numeric>

#include <complex>

#include <stack>

#include <queue>

#include <list>

#include <set>

#include <map>

#include <bitset>

#include <functional>

#include <iterator>



using namespace std;



#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl

#define repi(i,a,b) for(int i=int(a);i<int(b);i++)

#define peri(i,a,b) for(int i=int(b);i-->int(a);)

#define rep(i,n) repi(i,0,n)

#define per(i,n) peri(i,0,n)

#define iter(c) __typeof__((c).begin())

#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)

#define all(c) (c).begin(),(c).end()

#define mp make_pair



typedef unsigned int uint;

typedef long long ll;

typedef unsigned long long ull;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef vector<double> vd;

typedef vector<vd> vvd;

typedef vector<string> vs;

typedef pair<int,int> pii;



const int INFTY=1<<29;

const double EPS=1e-9;



template<typename T1,typename T2>

ostream& operator<<(ostream& os,const pair<T1,T2>& p){

	return os<<'('<<p.first<<','<<p.second<<')';

}

template<typename T>

ostream& operator<<(ostream& os,const vector<T>& a){

	os<<'[';

	rep(i,a.size()) os<<(i?" ":"")<<a[i];

	return os<<']';

}



int gcd(int a,int b)

{

	return b?gcd(b,a%b):a;

}



struct Edge{

	int src,dst;

	Edge(){}

	Edge(int s,int d):src(s),dst(d){}

};

typedef vector<vector<Edge> > Graph;



bool BFS(const Graph& g,const vi& side,const vi& match,vi& level)

{

	int n=g.size();

	level.assign(n,n);

	queue<pii> q;

	rep(i,n) if(side[i]==0 && match[i]==-1)

		q.push(mp(i,0));

	bool res=false;

	while(!q.empty()){

		pii cur=q.front(); q.pop();

		int u=cur.first,l=cur.second;

		if(level[u]<=l) continue;

		level[u]=l;

		rep(i,g[u].size()){

			int v=g[u][i].dst;

			if(match[v]==-1)

				res=true;

			else

				q.push(mp(match[v],l+2));

		}

	}

	return res;

}



bool DFS(const Graph& g,const vi& side,int u,vi& match,vi& level)

{

	rep(i,g[u].size()){

		int v=g[u][i].dst;

		if(match[v]==-1 || level[match[v]]>level[u] && DFS(g,side,match[v],match,level)){

			match[u]=v;

			match[v]=u;

			return true;

		}

	}

	level[u]=-1;

	return false;

}



int HopcroftKarp(const Graph& g,const vi& side,vi& match)

{

	int n=g.size();

	match.assign(n,-1);

	int res=0;

	for(vi level;BFS(g,side,match,level);)

		rep(i,n) if(side[i]==0 && match[i]==-1)

			res+=DFS(g,side,i,match,level);

	return res;

}



int main()

{

	for(int m,n;scanf("%d%d",&m,&n),m|n;){

		vi bs(m),rs(n);

		rep(i,m) scanf("%d",&bs[i]);

		rep(i,n) scanf("%d",&rs[i]);

		

		Graph g(m+n);

		rep(i,m) rep(j,n) if(gcd(bs[i],rs[j])>1){

			g[i].push_back(Edge(i,m+j));

			g[m+j].push_back(Edge(m+j,i));

		}

		

		vi side(m+n),match;

		fill(m+all(side),1);

		printf("%d\n",HopcroftKarp(g,side,match));

	}

	

	return 0;

}