/*
 * Copyright (c) 2009 Kamo Hiroyasu
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * ACM ICPC 2009 Japan Domestic Contest,
 *  Problem E  Cards
 *  Author: Kamo Hiroyasu <wd@ics.nara-wu.ac.jp>
 */

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int
gcd(int x, int y)
{
	while (y != 0) {
		int	z = x % y;
		x = y;
		y = z;
	}
	return x;
}

bool
visit(int i, const vector<vector<int> > &edges,
      vector<int> &op, vector<bool> &visited)
{
	if(visited[i]) return false;
	visited[i] = true;
	for(vector<int>::const_iterator j = edges[i].begin();
	    j != edges[i].end(); j ++) {
		int	k = *j;
		if(visited[k])
			continue;
		visited[k] = true;
		if(op[k] < 0 || visit(op[k], edges, op, visited)) {
			op[k] = i;
			op[i] = k;
			return true;
		}
	}
	return false;
}

int
solve(const vector<int> cards, int m, int n)
{
	vector<vector<int> >	edges(m + n);
	for(int i = 0; i < m; i ++) {
		for(int j = 0; j < n; j ++) {
			if(gcd(cards[i], cards[m+j]) != 1) {
				edges[i].push_back(m + j);
				edges[m+j].push_back(i);
			}
		}
	}
	vector<int>	op(m + n, -1);
	int	count = 0;
	for (;;) {
		int	oldcount = count;
		for(int i = 0; i < m; i ++){
			if(op[i] >= 0)
				continue;
			vector<bool>	visited(m + n, false);
			if (visit(i, edges, op, visited)) {
				count++;
			}
		}
		if (count == oldcount)
			break;
	}
	return count;
}

int
main()
{
	for(int m, n; cin >> m >> n && !(m == 0 && n == 0); ) {
		vector<int>	cards(m + n);
		for (int i = 0; i < m + n; i ++) {
			cin >> cards[i];
		}
		std::cout << solve(cards, m, n) << std::endl;
	}
	return 0;
}