// 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.2323250298303587x):
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <climits>

#include <cmath>

#include <cassert>

#include <iostream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <numeric>

#include <complex>

#include <list>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <bitset>

#include <utility>

#include <functional>

#include <iterator>



using namespace std;



#define dump(n) cerr<<"# "<<#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;



struct Edge{

	int src,dst;

	Edge(){}

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

};

typedef vector<vector<Edge> > Graph;



bool DFS(const Graph& g,int cur,vi& vis,vi& match)

{

	foreach(e,g[cur]){

		if(vis[e->dst])

			continue;

		vis[e->dst]=1;

		if(match[e->dst]==-1 || DFS(g,match[e->dst],vis,match)){

			match[e->src]=e->dst;

			match[e->dst]=e->src;

			return true;

		}

	}

	return false;

}



int BipertiteMatching(const Graph& _g)

{

	int size=_g.size();

	Graph g=_g;

	rep(i,size) foreach(e,_g[i])

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

	

	vi vis(size),match(size,-1);

	int res=0;

	rep(i,size)

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

			fill(all(vis),0);

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

		}

	return res;

}



int main()

{

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

		vi rs(m),bs(n);

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

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

		

		Graph g(m+n);

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

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

		int res=BipertiteMatching(g);

		printf("%d\n",res);

	}

	

	return 0;

}