#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

int gcd(int a, int b) {
	if (!b)return a;
	return gcd(b, a%b);
}
int b[500], r[500];
vector<int>E[500];
bool used[1000];
int match[1000];

bool dfs(int u) {
	used[u] = true;
	for (int v : E[u]) {
		int w = match[v];
		if (w == -1 || (!used[w] && dfs(w))) {
			match[u] = v; match[v] = u;
			return true;
		}
	}
	return false;
}
int main() {
	int m, n;
	while (scanf("%d%d", &m, &n), m) {
		rep(i, m)E[i].clear();
		rep(i, m)scanf("%d", &b[i]);
		rep(i, n)scanf("%d", &r[i]);
		rep(i, m)rep(j, n) {
			if (gcd(b[i], r[j]) != 1)E[i].push_back(m + j);
		}
		memset(match, -1, sizeof(match));
		int ans = 0;
		rep(i, m) {
			if (match[i] == -1) {
				memset(used, 0, sizeof(used));
				if (dfs(i))ans++;
			}
		}
		printf("%d\n", ans);
	}
}