#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

class pass
{
public:
	ll t;
	ll c;
	ll p;
};

class dinic
{
private:
	ll v, e;

	pass* p;

	vector<pair<ll, ll>>* node;

	ll* jun;

	void bfs()
	{
		queue<ll> q;
		stack<ll> st;
		for (ll i = 0; i < v; i++)
		{
			jun[i] = -1;
		}
		q.push(0);
		jun[0] = 0;
		while (!q.empty())
		{
			ll np = q.front();
			q.pop();
			st.push(np);
			for (int i = 1; i < node[np].size(); i++)
			{
				ll w = node[np][i].second;
				if (p[w].c > 0 && jun[p[w].t] < 0)
				{
					q.push(p[w].t);
					jun[p[w].t] = jun[np] + 1;
				}
			}
		}
		while (!st.empty())
		{
			ll np = st.top();
			st.pop();
			ll mae = 0;
			for (ll i = 1; i < node[np].size(); i++)
			{
				ll w = node[np][i].second;
				if (p[w].c > 0 && jun[p[w].t] == jun[np] + 1 && (p[w].t == v - 1 || node[p[w].t][0].first > 0))
				{
					node[np][mae].first = i;
					mae = i;
				}
			}
			node[np][mae].first = -1;
		}
	}

	pair<bool, ll> dfs(ll n, ll s)
	{
		if (n == v - 1)
		{
			return make_pair(false, s);
		}
		ll mae = 0;
		ll now = node[n][0].first;
		ll all = 0;
		while (now > 0 && s - all > 0)
		{
			ll w = node[n][now].second;
			auto r = dfs(p[w].t, min(p[w].c, s - all));
			p[p[w].p].c += r.second;
			p[w].c -= r.second;
			all += r.second;
			if (p[w].c == 0)
			{
				r.first = true;
			}
			if (r.first)
			{
				node[n][mae].first = node[n][now].first;
			}
			else
			{
				mae = now;
			}
			now = node[n][now].first;
		}
		node[n][mae].first = -1;
		if (mae == 0)
		{
			return make_pair(true, all);
		}
		else
		{
			return make_pair(false, all);
		}
	}
public:
	void set(ll vw, ll ew)
	{
		v = vw;
		p = new pass[ew * 2];
		node = new vector<pair<ll, ll>>[v];
		jun = new ll[v];
		e = 0;
		for (ll i = 0; i < v; i++)
		{
			node[i].push_back(make_pair(0, 0));
		}
	}

	void add(ll f, ll t, ll c)
	{
		p[e].t = t;
		p[e].c = c;
		p[e].p = e + 1;
		p[e + 1].t = f;
		p[e + 1].c = 0;
		p[e + 1].p = e;
		node[f].push_back(make_pair(0, e));
		node[t].push_back(make_pair(0, e + 1));
		e += 2;
	}

	ll solve()
	{
		while (1)
		{
			bfs();
			if (node[0][0].first < 0)
			{
				break;
			}
			dfs(0, ((ll)1 << 50));
		}
		ll all = 0;
		for (int i = 1; i < node[0].size(); i++)
		{
			auto w = node[0][i];
			if (w.second % 2 == 0)
			{
				all += p[p[w.second].p].c;
			}
		}
		return all;
	}

	void del()
	{
		delete[] p;
		delete[] node;
		delete[] jun;
	}
};

ll dn[2000];
ll dm[2000];

ll gcd(ll a, ll b)
{
	if (a % b == 0)
	{
		return b;
	}
	return gcd(b, a % b);
}

int main()
{
	while (1)
	{
		dinic a;
		ll n, m;
		scanf("%lld%lld", &n, &m);
		if (n == 0)
		{
			break;
		}
		a.set(n + m + 2, n * m * 2);
		for (ll i = 0; i < n; i++)
		{
			scanf("%lld", &dn[i]);
			a.add(0, 1 + i, 1);
		}
		for (ll i = 0; i < m; i++)
		{
			scanf("%lld", &dm[i]);
			a.add(n + 1 + i, n + m + 1, 1);
		}
		for (ll i = 0; i < n; i++)
		{
			for (ll ii = 0; ii < m; ii++)
			{
				if (1 < gcd(dn[i], dm[ii]))
				{
					a.add(1 + i, n + 1 + ii, 1);
				}
			}
		}
		printf("%lld\n", a.solve());
		a.del();
	}
	return 0;
}

Measured memory_bytes: 22104