#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define rep(i,n) for(int i = 0;i < n;i++)
#define clr(n)	memset(n,0,sizeof(n));
const int INF = 1e9;

int gcd(int a, int b) {
	return b ? gcd(b, a%b) : a; 
}

struct edge { int to, cap, rev; };
vector<edge> G[1001];
bool used[1001];

void clear() {
	rep(i, 1001) {
		G[i].clear();
		used[i] = false;
	}
}

void add_edge(int from, int to, int cap) {
	G[from].push_back(edge{ to, cap, int(G[to].size()) });
	G[to].push_back(edge{ from, 0, int(G[from].size()) - 1 });
}

int dfs(int v, int t, int f) {
	if (v == t)return f;
	used[v] = true;
	rep(i, G[v].size()) {
		edge &e = G[v][i];
		if (!used[e.to] && e.cap > 0) {
			int d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s, int t) {
	int flow = 0;
	for (;;) {
		clr(used);
		int f = dfs(s, t, INF);
		if (f == 0)return flow;
		flow += f;
	}
}

int main() {
	int m, n;

	while (cin >> m >> n && m) {
		vector<int> r(m), b(n);
		clear();
		rep(i, m) {
			cin >> r[i];
			add_edge(m + n, i, 1);
		}
		rep(i, n) {
			cin >> b[i];
			add_edge( m + i, m + n + 1, 1);
		}
		rep(i, m)rep(j, n) {
			if (gcd(r[i], b[j]) != 1) {
				add_edge(i, m + j, 1);
			}
		}

		cout << max_flow(m + n, m + n + 1) << endl;
	}
	return 0;
}