// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <string>

#include <stack>

#include <queue>

#include <deque>

#include <set>

#include <map>

#include <algorithm>	// require sort next_permutation count __gcd reverse etc.

#include <cstdlib>	// require abs exit atof atoi 

#include <cstdio>		// require scanf printf

#include <functional>

#include <numeric>	// require accumulate

#include <cmath>		// require fabs

#include <climits>

#include <limits>

#include <cfloat>

#include <iomanip>	// require setw

#include <sstream>	// require stringstream 

#include <cstring>	// require memset

#include <cctype>		// require tolower, toupper

#include <fstream>	// require freopen

#include <ctime>		// require srand

#define rep(i,n) for(int i=0;i<(n);i++)

#define ALL(A) A.begin(), A.end()

#define INF 1<<29



using namespace std;



const int MAX_V = 1005;

// 辺を表す構造体（行き先、容量、逆辺）

struct edge{ int to, cap, rev; };



vector<edge> G[MAX_V];	// グラフの隣接リスト表現

bool used[MAX_V];			// DFS ですでに調べたかのフラグ



// from から to へ向かう容量 cap の辺をグラフに追加する

void add_edge (int from, int to, int cap ){

	G[from].push_back ((edge){to, cap, G[to].size() } );

	G[to].push_back ((edge){from, 0, G[from].size()-1 } );

}



// 増加バスを DFS で探す

int dfs (int v, int t, int f ){

	if (v == t ) return f;

	used[v] = true;

	for (int i = 0; i < G[v].size(); i++ ){

		edge &e = G[v][i];

		if (!used[e.to] && e.cap > 0 ){

			int d = dfs (e.to, t, min (f, e.cap ) );

			if (d > 0 ){

				e.cap -= d;

				G[e.to][e.rev].cap += d;

				return d;

			} // end if

		} // end if

	} // end for



	return 0;

}



// s から t への最大流を求める

int max_flow (int s, int t ){

	int flow = 0;

	for (;; ){

		memset (used, false, sizeof (used ) );

		int f = dfs (s, t, INF );

		if (f == 0 ) return flow;

		flow += f;

	} // end for

}



int main()

{

//	cut here before submit 

//	freopen ("testcase.1163", "r", stdin );

	int n, m;

	while (scanf ("%d %d", &n, &m ), n, m ){

		rep (i, MAX_V ) G[i].clear();

		// 0 〜 n-1: bule card n〜n+m-1: red card

		// n+m : source n+m+1: sink

		vector<int> cards (n+m, 0 );

		rep (i, n ){

			scanf ("%d", &cards[i] );

			add_edge(n+m, i, 1 );

		} // end rep

		rep (j, m ){

			scanf ("%d", &cards[n+j] );

			add_edge(n+j, n+m+1, 1 );

		} // end rep



		rep (i, n ){

			rep (j, m ){

				if (__gcd (cards[i], cards[n+j] ) != 1 ){

					add_edge (i, n+j, 1 );

				} // end if

			} // end rep

		} // end rep

		int res = max_flow (n+m, n+m+1 );

		printf ("%d\n", res );

	} // end while

		

	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <string>

#include <stack>

#include <queue>

#include <deque>

#include <set>

#include <map>

#include <algorithm>	// require sort next_permutation count __gcd reverse etc.

#include <cstdlib>	// require abs exit atof atoi 

#include <cstdio>		// require scanf printf

#include <functional>

#include <numeric>	// require accumulate

#include <cmath>		// require fabs

#include <climits>

#include <limits>

#include <cfloat>

#include <iomanip>	// require setw

#include <sstream>	// require stringstream 

#include <cstring>	// require memset

#include <cctype>		// require tolower, toupper

#include <fstream>	// require freopen

#include <ctime>		// require srand

#define rep(i,n) for(int i=0;i<(n);i++)

#define ALL(A) A.begin(), A.end()

#define INF 1<<29



using namespace std;

/*

	二部マッチング



	説明

		二部グラフの最大マッチングを求める Ford-Fulerson like なアルゴリズム

		bipartite_matching がメインルーチン



	引数

		L : 左の頂点集合のサイズ

		R : 右の頂点集合のサイズ

		G : 二部グラフ（表示方法が特殊なので注意）

			G[0],...,G[L-1] まであり、G[u] は u と辺でつながっている右の頂点集合を表す。

			ここで、右の頂点は 0,...,R-1 と番号付けられている。



	戻り値

		最大マッチングのサイズ

	

	制約

		なし

	

	計算量

		O(V*(V+E))



	備考

		V_MAX は max(L,R) 以上であればよい。



		マッチングが具体的にほしいときは match を返すようにする

		match[0][u] := 左の頂点 u とマッチしている右の頂点の番号（存在しなければ -1 ）

		match[1][v] := 右の頂点 v とマッチしている左の頂点の番号（存在しなければ -1 ）



*/

const int V_MAX=500;



bool augment(int u,bool *vis,int match[2][V_MAX], const vector<int> *G ){

	if(u==-1) return true;



	rep(i,G[u].size()){

		int v=G[u][i];

		if(!vis[v]){

			vis[v]=true;

			if(augment(match[1][v],vis,match,G)){

				match[0][u]=v;

				match[1][v]=u;

				return true;

			} // end if

		} // end if

	} // end rep

	return false;

}



int bipartite_matching(int L,int R,const vector<int> *G){

	static int match[2][V_MAX];

	rep(u,L) match[0][u]=-1;

	rep(v,R) match[1][v]=-1;

	

	int res=0;

	static bool vis[V_MAX];

	rep(u,L){

		rep(v,R) vis[v]=false;

		if(augment(u,vis,match,G)) res++;

	} // end rep



	return res;

}

int main()

{

//	cut here before submit 

//	freopen ("testcase.1163", "r", stdin );

	int n, m;

	while (scanf ("%d %d", &n, &m ), n, m ){

		static vector<int> G[V_MAX];

		rep (i, V_MAX ) G[i].clear();

		// 0 〜 n-1: bule card n〜n+m-1: red card

		vector<int> cards (n+m, 0 );

		rep (i, n ){

			scanf ("%d", &cards[i] );

		} // end rep

		rep (j, m ){

			scanf ("%d", &cards[n+j] );

		} // end rep



		rep (i, n ){

			rep (j, m ){

				if (__gcd (cards[i], cards[n+j] ) != 1 ){

					G[i].push_back (j );

				} // end if

			} // end rep

		} // end rep

		int res = bipartite_matching (n, m, G );

		printf ("%d\n", res );

	} // end while

		

	return 0;

}

// Fastest known solution for this problem: