#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include <map>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include"time.h"
using namespace std;

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define LL long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define dump(x)  cerr << #x << " = " << (x) << endl

/*
using Weight = int;
using Flow = int;
struct Edge {
	int src, dst;
	Weight weight;
	Flow cap;
	Edge() : src(0), dst(0), weight(0) {}
	Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
	g[a].emplace_back(a, b, w);
	g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }

*/

class bipartite_matching {
public:
	int n;
	vector<vector<int>> g;
	vector<int> match;

	bipartite_matching(int n_) : n(n_), g(n_), match(n_), used(n_) {}

	void add_edge(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}

	int maximum_matching(void) {
		int res = 0;
		fill(match.begin(),match. end(), -1);
		for (int v = 0; v < n; ++v) {
			if (match[v] == -1) {
				fill(begin(used), end(used), false);
				if (dfs(v)) res++;
			}
		}
		return res;
	}

private:
	vector<int> used;
	bool dfs(int v) {
		used[v] = true;
		for (int u : g[v]) {
			int w = match[u];
			if (w == -1 || (!used[w] && dfs(w))) {
				match[v] = u;
				match[u] = v;
				return true;
			}
		}
		return false;
	}
};


//?????????????????´???
#define NM_MAX 500


//??????????????¨??????
int m,n;
int b[NM_MAX];
int r[NM_MAX];

//b,r????????????????´??????°
set<int> primeB[NM_MAX];
set<int> primeR[NM_MAX];


int main() {
	while(1){
		//?????????
		CLR(b);
		CLR(r);
		REP(i, NM_MAX)primeB[i].clear();
		REP(i, NM_MAX)primeR[i].clear();

		//??\???????????????
		cin>>m>>n;
		if(m==0 && n==0)break;
		REP(i, m)cin >> b[i];
		REP(i, n)cin >> r[i];

		//?´??????°????§£
		int prime;
		REP(i, m) {
			prime=2;
			while (prime <= sqrt(b[i])) {
				//cout<<prime<<"  "<<b[i]<<endl;
				if (b[i] % prime == 0) {
					b[i]/=prime;

					primeB[i].insert(prime);
				}
				else {
					prime++;
				}
			}
			primeB[i].insert(b[i]);

		}	

		REP(i, n) {
			prime = 2;
			while (prime <= sqrt(r[i])) {

				if (r[i] % prime == 0) {
					r[i] /= prime;
					primeR[i].insert(prime);
				}
				else {
					prime++;
				}
			}

			primeR[i].insert(r[i]);
		}

		//???????????£?????????
		bipartite_matching bm = bipartite_matching(m + n + 1);
		bool okFlag;//???????????????????????????
		REP(i, m)REP(j, n) {
			okFlag=false;

			for (set<int>::iterator it = primeB[i].begin(); it != primeB[i].end(); it++) {

				//?????´??????????´?????????£?????´???
				if (primeR[j].find(*it) != primeR[j].end()) {
					okFlag=true;
					break;
				}
			}
			if(okFlag)bm.add_edge(i,m+j);
		}

		//??????????????§??????????????°????±?????????????
		int ans=bm.maximum_matching();

		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 4684