#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;

const int my_inf=2147483647;
const long long int my_linf=9223372036854775807;



#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;
struct Edge {
	int src, dst;
	Weight weight;
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
};
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])

//流量0の逆辺も張らないと正しく求まらないので注意
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, 0));
			}
		}
	}
	int n = g.size();
	Matrix flow(n, Array(n)), capacity(n, Array(n));
	REP(u, n) FOR(e, g[u]) capacity[e->src][e->dst] += e->weight;


	Weight total = 0;
	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) > 0) {
				prev[e->dst] = u;
				Q.push(e->dst);
			}
		}
		if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side
		Weight inc = INF;
		for (int j = t; prev[j] != j; j = prev[j])
			inc = min(inc, RESIDUE(prev[j], j));
		for (int j = t; prev[j] != j; j = prev[j])
			flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc;
		total += inc;
	}
}

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 {
		if (r%l) {
			return gcd(l, r%l);

		}
		else {
			return l;
		}
	}
}

int main() {
	while (1) {


		int m, n; cin >> m >> n;
		if (!m)break;
		vector<int>blues, reds;
		for (int i = 0; i < m; ++i) {
			int a; cin >> a;
			blues.push_back(a);
		}
		for (int j = 0; j < n; ++j) {
			int a; cin >> a;
			reds.push_back(a);
		}
		const int start = 0;
		const int bluea = 1;
		const int blueb = bluea + m;
		const int reda = blueb + m;
		const int redb = reda + n;
		const int goal = redb + n;
		Graph g(goal + 1);
		for (int i = 0; i < m; ++i) {
			g[start].push_back(Edge(start, bluea + i, 1));
			g[bluea + i].push_back(Edge(bluea + i, blueb + i, 1));
		}

		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (gcd(blues[i], reds[j]) != 1) {
					g[blueb + i].push_back(Edge(blueb + i, reda + j, 1));
				}
			}
		}

		for (int i = 0; i < n; ++i) {
			g[reda + i].push_back(Edge(reda + i, redb + i, 1));
			g[redb + i].push_back(Edge(redb + i, goal, 1));

		}
		int ans = maximumFlow(g, start, goal);
		cout << ans << endl;

	}
	return 0;
}

Measured memory_bytes: 41408