#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

template<int NN> class BipartiteMatch
{
	public:
	BipartiteMatch()
	{
		memset(matchedTo, -1, sizeof(matchedTo));
	}
	vector<int> edge[NN];
	void add(int a, int b)
	{
		edge[a].push_back(b);
		edge[b].push_back(a);
		//cout << a << ", " << b << endl;
	}
	int matchedTo[NN];
	bool augment(int s)
	{
		memset(visited, 0, sizeof(visited));
		return aug(s);
	}
	bool visited[NN];
	private:
	bool aug(int s)
	{
		if(s<0){
			return true;
		}
		for(int i=0;i<edge[s].size();i++){
			int t=edge[s][i];
			if(!visited[t]){
				visited[t]=true;
				if (aug(matchedTo[t])){
					matchedTo[t]=s;
					return true;
				}
			}
		}
		return false;
	}
};

int gcd(int a,int b){
	while(b){
		int r=a%b;
		a=b;
		b=r;
	}
	return a;
}
int m,n;
int b[500];
int r[500];
int main() {
	while(1){
	cin >> m >> n;
	if(m==0&&n==0)return 0;
	BipartiteMatch<1000> bm;
	for(int i=0;i<m;i++){
		cin >> b[i];
	}
	for(int i=0;i<n;i++){
		cin >> r[i];
		for(int j=0;j<m;j++){
			if(gcd(r[i],b[j])>1){
				bm.add(i+m,j);
			}
		}
	}
	int ret=0;
	for(int i=0;i<m;i++){
		if(bm.augment(i)){
			ret++;
		}
	}
	cout << ret << endl;
	}
}