#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 30000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 998244353LL
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
long long powering(long long now,long long now_go){
	long long ans = 1;
	while (now_go != 0) {
		if (now_go % 2 == 1) {
			ans *= now;
			ans %= MAX_MOD;
		}
		now *= now;
		now %= MAX_MOD;
		now_go /= 2;
	}
	return ans;
}
vector<long long> calc(vector<long long> a, vector<long long> b) {
	long long k = sqrt(a.size());
	vector<long long> ans;
	for (int i = 0; i < k; ++i) {
		for (int q = 0; q < k; ++q) {
			//ans[i][q]を計算する
			long long geko = 0;
			for (int t = 0; t < k; ++t) {
				geko += a[i * k + t] * b[t * k + q];
				geko %= MAX_MOD;
 			}
			ans.push_back(geko);
		}
	}
	return ans;
}
vector<long long> powered(vector<long long> a, long long n) {
	vector<long long> ans = a;
	n--;
	while (n != 0) {
		if (n % 2 == 1) {
			ans = calc(ans, a);
		}
		a = calc(a, a);
		n /= 2;
	}
	return ans;
}
long long inv(long long now) {
	return powering(now, MAX_MOD - 2LL);
}
long long dping[1002][1002] = {};
vector<int>  dp_move[1002];
int visited[1002] = {};
int solve(int now) {
	if (now == 1001) return 1;
	for (int i = 0; i < dp_move[now].size(); ++i) {
		if (visited[dp_move[now][i]] == 0) {
			if (dping[now][dp_move[now][i]] > 0) {
				visited[dp_move[now][i]] = 1;
				int geko = solve(dp_move[now][i]);
				if (geko == 1) {
					dping[now][dp_move[now][i]]--;
					if(now != 1000)
					dping[dp_move[now][i]][now]++;
					return 1;
				}
			}
		}
	}
	return 0;
}
long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main(){
#define int long long
	while (true) {
		int n, m;
		cin >> n >> m;
		if (n == 0) return 0;
		vector<int> a, b;
		REP(i, n) {
			int c;
			cin >> c;
			a.push_back(c);
		}
		REP(i, m) {
			int c;
			cin >> c;
			b.push_back(c);
		}
		REP(i, 1002) {
			dp_move[i].clear();
		}
		REP(i, 1002) {
			REP(q, 1002) {
				dping[i][q] = 0;
			}
		}
		for (int i = 0; i < n; ++i) {
			for (int q = 0; q < m; ++q) {
				if (gcd(a[i],b[q]) > 1) {
					dp_move[i].push_back(500 + q);
					dp_move[500 + q].push_back(i);
					dping[i][500 + q] = 1;
				}
			}
			dping[1000][i] = 1;
			dp_move[1000].push_back(i);
			dp_move[i].push_back(1000);
		}
		REP(i, m) {
			dping[i + 500][1001] = 1;
			dp_move[i + 500].push_back(1001);
		}
		REP(i, 1002) {
			visited[i] = 0;
		}
		visited[1000] = 1;
		int ans = 0;
		while (solve(1000)) {
			REP(i, 1002) {
				visited[i] = 0;
			}
			visited[1000] = 1;
			ans++;
		}
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 12792