#include"bits/stdc++.h"
using namespace std;

//define
#define ALL(a) a.begin(),a.end()
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define debug(x) if(1)cout<<#x<<":"<<x<<endl;
#define DEBUG(x) if(1)cout<<#x<<":"<<x<<endl;
#define ll long long

//constant
const int MOD = 1000000009;
const int INF = INT_MAX / 3;

//typedef
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

struct edge { int to, cap, rev, cost; };

constexpr int MAX_V = 1002;
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

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

void bfs(int s) {
	fill_n(level, MAX_V, -1);
	queue<int> que;
	level[s] = 0;
	que.push(s);
	while (!que.empty()) {
		int v = que.front(); que.pop();
		for (int i = 0; i < G[v].size(); i++) {
			edge &e = G[v][i];
			if (e.cap > 0 && level[e.to] < 0) {
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}
int dfs(int v, int t, int f) {
	if (v == t)return f;
	for (int &i = iter[v]; i < G[v].size(); i++) {
		edge &e = G[v][i];
		if (e.cap > 0 && level[v] < level[e.to]) {
			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 (;;) {
		bfs(s);
		if (level[t] < 0)return flow;
		fill_n(iter, MAX_V, 0);
		int f;
		while ((f = dfs(s, t, numeric_limits<int>::max()))>0) {
			flow += f;
		}
	}
}

typedef pair<int, int> P;
int V;
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];

int min_cost_flow(int s, int t, int f) {
	int res = 0;
	fill_n(h, V, 0);
	while (f > 0) {
		priority_queue<P, vector<P>, greater<P>> que;
		fill_n(dist, V, numeric_limits<int>::max());
		dist[s] = 0;
		que.push({ 0,s });
		while (!que.empty()) {
			P p = que.top(); que.pop();
			int v = p.second;
			if (dist[v] < p.first)continue;
			for (int i = 0; i < G[v].size(); i++) {
				edge &e = G[v][i];
				if (e.cap > 0 && dist[e.to]>dist[v] + e.cost + h[v] - h[e.to]) {
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push({ dist[e.to],e.to });
				}
			}
		}
		if (dist[t] == numeric_limits<int>::max()) {
			return -1;
		}
		for (int v = 0; v < V; v++)h[v] += dist[v];

		int d = f;
		for (int v = t; v != s; v = prevv[v]) {
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d*h[t];
		for (int v = t; v != s; v = prevv[v]) {
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return res;
}

int gcd(int x, int y) {
	if (y == 0 || x == 0)
		return max(x, y);
	y = y - (y / x)*x;
	return gcd(y, x);

}
int main() {
	int m, n;
	vector<int> prime;
	vector<int> isprime(50000, 1);
	isprime[0] = isprime[1] = 0;
	for (int i = 0; i < 50000; i++)
		if (isprime[i]) {
			prime.push_back(i);
			for (int j = i * 2; j < 50000; j += i)
				isprime[j] = 0;


		}
	while (cin >> m >> n, m) {
		for (int i = 0; i < MAX_V; i++)
			G[i].clear();
		vector<int> b(m);
		vector<int> r(n);
		REP(i, m)
			cin >> b[i];
		REP(i, n)
			cin >> r[i];
		REP(i, m) {
			add_edge(n + m, i, 1);

		}
		REP(j, n) {
			add_edge(j + m, m + n + 1, 1);
		}
		REP(i, m)
			REP(j, n) {
			if (gcd(b[i], r[j]) != 1)
				add_edge(i, j + m, 1);
		}
		cout << max_flow(n + m, n + m + 1) << endl;
	}
	


}

Measured memory_bytes: 11856