#include "bits/stdc++.h"
using namespace std;
using ld = long double;
const ld eps = 1e-9;



#define _GLIBCXX_DEBUG

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()


//const int INF = 2147483647;
//const long long int L_INF = 9223372036854775807;

typedef int Weight;

const Weight INF = 1e9;
const Weight ZERO = 0;
struct Edge {
	int src, dst;
	Weight weight;
	int id;
	Edge(int src_, int dst_, Weight weight_, const int id_) :
		src(src_), dst(dst_), weight(weight_), id(id_) { }
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
	Edge() :src(0), dst(0), weight(0) {

	}
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;
#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])

//テヲツオツ?ゥツ??テ」ツ?ョテゥツ??ィツセツコテ」ツつづ・ツシツオテ」ツつ嘉」ツ?ェテ」ツ??」ツ?ィテヲツュツ」テ」ツ?療」ツ?湘ヲツアツづ」ツ?セテ」ツつ嘉」ツ?ェテ」ツ??」ツ?ョテ」ツ?ァテヲツウツィテヲツ??
Weight maximumFlow(const Graph &ag, int s, int t) {

	Graph g(ag);
	for (int i = 0; i < ag.size(); ++i) {
		for (int j = 0; j < ag[i].size(); ++j) {
			int d = ag[i][j].dst;
			int s = ag[i][j].src;

			bool ok = false;
			for (int k = 0; k < ag[d].size(); ++k) {
				if (ag[d][k].src == s) {
					ok = true;
					break;
				}
			}
			if (!ok) {
				g[d].push_back(Edge(d, s, ZERO));
			}
		}
	}
	int n = g.size();
	Matrix flow(n, Array(n,ZERO)), capacity(n, Array(n,ZERO));
	REP(u, n) FOR(e, g[u]) capacity[e->src][e->dst] =capacity[e->src][e->dst]+ e->weight;


	Weight total = ZERO;
	while (1) {
		queue<int> Q; Q.push(s);
		vector<int> prev(n, -1); prev[s] = s;
		while (!Q.empty() && prev[t] < 0) {
			int u = Q.front(); Q.pop();
			FOR(e, g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > ZERO) {
				prev[e->dst] = u;
				Q.push(e->dst);
			}
		}
		if (prev[t] < 0)break; // prev[x] == -1 <=> t-side
		Weight inc = INF;
		for (int j = t; prev[j] != j; j = prev[j]){
			auto v(RESIDUE(prev[j], j));
			if (inc > v) {
				inc = v;
			}
		}
		for (int j = t; prev[j] != j; j = prev[j])
			flow[prev[j]][j] =flow[prev[j]][j]+inc, flow[j][prev[j]] =flow[j][prev[j]]- inc;;
		total += inc;
	}

	return total;
}

long long int gcd(long long int l, long long int r) {
	assert(l > 0 && r > 0);
	if (l > r)return gcd(r, l);
	else {
		const long long int num = r%l;
		if (num) {
			return gcd(l, num);
		}
		else {
			return l;
		}
	}
}

int main() {
	while (1) {
		int M, N; cin >> M >> N;
		if (!M)break;
		vector<int>as(M), bs(N);
		for (int i = 0; i < M; ++i) {
			cin >> as[i];
		}
		for (int j = 0; j < N; ++j) {
			cin >> bs[j];
		}

		const int start = 0;
		const int blue = 1;
		const int red = blue + M;
		const int goal = red + N;
		Graph g(goal + 1);
		for (int i = 0; i < M; ++i) {
			g[start].push_back(Edge(start, blue + i, 1));
		}
		for (int i = 0; i < M; ++i) {
			for (int j = 0; j < N; ++j) {
				if (gcd(as[i],bs[j])!=1) {
					g[blue + i].push_back(Edge(blue + i, red + j, 1));
				}
			}
		}
		for (int i = 0; i < N; ++i) {
			g[red + i].push_back(Edge(red + i, goal, 1));
		}
		int ans = maximumFlow(g, start, goal);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 19892