#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <cstdio>

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
#define REV(s) (s).rbegin(), (s).rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define MT make_tuple
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

// FordFulkerson:Verified: POJ 1274
// Dinic:Verified: POJ 1274, 3469

class Flow{
	struct edge{
		int to, rev, cap, cost;
		edge(){}
		edge(int to, int rev, int cap, int cost) :to(to), rev(rev), cap(cap), cost(cost){}
	};
	vector<vector<edge> > Graph;
	vector<int> used, level, iter;
	int V;
	static const int INF = 1 << 30;
public:
	Flow(int size) :V(size){
		Graph.resize(V);
		iter.resize(V, 0);
		level.resize(V);
		used.resize(V, 0);
	}
	void add(int from, int to, int cap, int cost = 0){
		Graph[from].push_back(edge(to, Graph[to].size(), cap, cost));
		Graph[to].push_back(edge(from, Graph[from].size() - 1, 0, -cost));
	}

	/* ford_fulkerson */
	int dfs(int s, int t, int f){
		if (s == t) return f;
		used[s] = 1;
		for (int i = 0; i < Graph[s].size(); i++){
			edge &e = Graph[s][i];
			if (used[e.to] || e.cap <= 0) continue;
			int res = dfs(e.to, t, min(f, e.cap));
			if (res > 0){
				e.cap -= res;
				Graph[e.to][e.rev].cap += res;
				return res;
			}
		}
		return 0;
	}

	int ford_fulkerson(int s, int t){
		int res = 0;
		while (1){
			fill(used.begin(), used.end(), 0);
			int f = dfs(s, t, INF);
			if (!f) break;
			res += f;
		}
		return res;
	}

	/* Dinic */
	void dinic_bfs(int s){
		fill(level.begin(), level.end(), -1);

		queue<int> q;
		q.push(s);
		level[s] = 0;
		while (!q.empty()){
			int v = q.front(); q.pop();
			for (int i = 0; i < Graph[v].size(); i++){
				edge &e = Graph[v][i];
				if (e.cap <= 0 || level[e.to] >= 0) continue;
				level[e.to] = level[v] + 1;
				q.push(e.to);
			}
		}
	}

	int dinic_dfs(int s, int t, int f){
		if (s == t) return f;
		for (int &i = iter[s]; i < Graph[s].size(); i++){
			edge &e = Graph[s][i];
			if (e.cap <= 0 || level[e.to] <= level[s]) continue;
			int res = dinic_dfs(e.to, t, min(f, e.cap));
			if (res > 0){
				e.cap -= res;
				Graph[e.to][e.rev].cap += res;
				return res;
			}
		}
		return 0;
	}

	int dinic(int s, int t){
		int res = 0;
		while (1){
			dinic_bfs(s);
			if (level[t] < 0) break;
			fill(iter.begin(), iter.end(), 0);
			int f;
			while (f = dinic_dfs(s, t, INF)){
				res += f;
			}
		}
		return res;
	}

	int max_flow(int s, int t, bool DINIC = true){
		if (DINIC) return dinic(s, t);
		return ford_fulkerson(s, t);
	}
};

ll gcd(ll m, ll n){
	return n ? gcd(n, m%n) : m;
}

int main(){
	int m, n;
	while (cin >> m >> n, m | n){
		Flow f(m + n + 2);
		const int SRC = m + n, SNK = SRC + 1;

		vector<int> a(m), b(n);
		rep(i, m){
			cin >> a[i];
			f.add(SRC, i, 1);
		}
		rep(j, n){
			cin >> b[j];
			f.add(m + j, SNK, 1);
		}

		rep(i, m) rep(j, n){
			if (gcd(a[i], b[j]) != 1) f.add(i, m + j, 1);
		}
		//cout << "***";
		cout << f.max_flow(SRC, SNK) << endl;
	}

	return 0;
}

Measured memory_bytes: 7040