#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){}
};

bool operator<(const Edge& lhs,const Edge& rhs)
{
	return lhs.weight<rhs.weight;
}

bool operator>(const Edge& lhs,const Edge& rhs)
{
	return lhs.weight>rhs.weight;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void BFS(const Graph& g,int begin,int end,const vvi& capacity,const vvi& flow,vi& label)
{
	queue<pii> q;
	q.push(mp(begin,0));
	while(!q.empty()){
		pii v=q.front(); q.pop();
		if(label[v.first]<=v.second)
			continue;
		label[v.first]=v.second;
		foreach(e,g[v.first])
			if(capacity[e->src][e->dst]-flow[e->src][e->dst]>0)
				q.push(mp(e->dst,v.second+1));
	}
}

int DFS(const Graph& g,int v,int end,const vvi& capacity,vvi& flow,vi& label,vi& finished,int f)
{
	if(v==end)
		return f;
	if(finished[v])
		return 0;
	finished[v]=true;
	
	foreach(e,g[v]){
		if(label[e->src]>=label[e->dst])
			continue;
		int r=capacity[e->src][e->dst]-flow[e->src][e->dst];
		if(r<=0)
			continue;
		int inc=DFS(g,e->dst,end,capacity,flow,label,finished,min(f,r));
		if(inc>0){
			flow[e->src][e->dst]+=inc;
			flow[e->dst][e->src]-=inc;
			finished[v]=false;
			return inc;
		}
	}
	
	return 0;
}

int Dinic(const Graph& _g,int begin,int end)
{
	int size=_g.size();
	
	// tûüÌÓðÁ¦é(eÊÍ0É·é)
	Graph g=_g;
	rep(i,size)
		foreach(e,_g[i])
			g[e->dst].push_back(Edge(e->dst,e->src,0));
	
	vvi capacity(size,vi(size)),flow(size,vi(size));
	rep(i,size)
		foreach(e,g[i])
			capacity[e->src][e->dst]+=e->weight;
	
	for(;;){
		vi label(size,INFTY);
		BFS(g,begin,end,capacity,flow,label);
		if(label[end]==INFTY)
			break;
		vi finished(size);
		while(DFS(g,begin,end,capacity,flow,label,finished,INFTY))
			;
	}
	
	return accumulate(allof(flow[begin]),0);
}

// [0,m): left, [m,gsize): right
int BiparateMatching(const Graph& _g,int m)
{
	int n=_g.size()-m;
	Graph g=_g;
	g.resize(g.size()+2);
	rep(i,m)
		g[m+n].push_back(Edge(m+n,i,1));
	rep(i,n)
		g[m+i].push_back(Edge(m+i,m+n+1,1));
	return Dinic(g,m+n,m+n+1);
}

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;
}

Measured memory_bytes: 17000