#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>

using namespace std;
typedef long long int LL;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
struct edge { LL to, cap, rev, cost; };

constexpr LL MAX_V = 1200;
vector<edge> G[MAX_V];
LL level[MAX_V];
LL iter[MAX_V];

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

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

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

LL min_cost_flow(LL s, LL t, LL f) {
	LL res = 0;
	fill_n(h, V, 0);
	while (f > 0) {
		priority_queue<P, vector<P>, greater<P>> que;
		fill_n(dist, V, numeric_limits<LL>::max());
		dist[s] = 0;
		que.push({ 0,s });
		while (!que.empty()) {
			P p = que.top(); que.pop();
			LL v = p.second;
			if (dist[v] < p.first)continue;
			for (LL 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<LL>::max()) {
			return -1;
		}
		for (LL v = 0; v < V; v++)h[v] += dist[v];

		LL d = f;
		for (LL v = t; v != s; v = prevv[v]) {
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d*h[t];
		for (LL 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;
}

bool hoge(LL s, LL t) {
	if (s%t == 0 || t%s == 0) { return true; }else
		if (s%t == 1 || t%s == 1) { return false; }
		else {
			return hoge(s%t, t%s);
		}
}

int main()
{
	while (true) {
		REP(i, MAX_V) {
			G[i].erase(G[i].begin(), G[i].end());
		}
		LL m, n;
		cin >> m >> n;
		if (m == 0 && n == 0) { break; }
		vector<LL>b(m + 1);
		vector<LL>r(n + 1);
		REP(i, m) {
			cin >> b[i];
			add_edge(0, i + 1, 1);
		}
		REP(j, n) {
			cin >> r[j];
			add_edge(m+j+1, n+m + 1, 1);
			REP(i, m) {
				if (hoge(b[i], r[j])) {
					add_edge(i + 1, m + j + 1, 1);
				}
			}
		}
		cout << max_flow(0, n + m + 1) << endl;
	}
}

Measured memory_bytes: 19656