// Slower C++ solution:
#include <iostream>

#include <vector>

#include <cstdio>

#include <complex>

#include <limits>

using namespace std;

typedef complex<double> P;



#define EPS (1e-10)

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

#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)

#define ALLOF(c) (c).begin(), (c).end()



typedef double Weight;

const Weight WEIGHT_INFTY = numeric_limits<Weight>::max() / 4;

struct Edge {

    int src, dst;

    Weight weight;

		Edge(int a,int b){

			src = a;

			dst = b;

		}

};

bool operator<(const Edge& a, const Edge& b) {

    return (a.weight < b.weight);

}

typedef vector<Edge> Edges;

typedef vector<Edges> Graph;



bool augment(const Graph& g, int u,

    vector<int>& matchTo, vector<bool>& visited) {

  if (u < 0) return true;

  FOR(e, g[u]) if (!visited[e->dst]) {

    visited[e->dst] = true;

    if (augment(g, matchTo[e->dst], matchTo, visited)) {

      matchTo[e->src] = e->dst;

      matchTo[e->dst] = e->src;

      return true;

    }

  }

  return false;

}

int bipartiteMatching(const Graph& g, int L, Edges& matching) {

  const int n = g.size();

  vector<int> matchTo(n, -1);

  int match = 0;

  REP(u, L) {

    vector<bool> visited(n);

    if (augment(g, u, matchTo, visited)) ++match;

  }

  REP(u, L) if (matchTo[u] >= 0) // make explicit matching

    matching.push_back( Edge(u, matchTo[u]) );

  return match;

}

 

int gcd(int x,int y){

	return y ? gcd(y,x%y) : x ;

}

int main(){

	int n,m;

	while(cin>>n>>m,n|m){

		vector<int> l,r;

		Graph g;

		REP(i,n){ int a; cin>>a; l.push_back(a); }

		REP(i,m){ int a; cin>>a; r.push_back(a); }

		

		REP(i,l.size()){

			vector<Edge> node;

			REP(j,r.size())if( gcd(l[i],r[j])>1 ){

				node.push_back( Edge(i,j+n) );

			}

			g.push_back( node );

		}

		REP(i,r.size()){

			vector<Edge> node;

			REP(j,l.size())if(gcd(r[i],l[j])>1){

				node.push_back( Edge(i+n,j) );

			}

			g.push_back( node );

		}

		/*

		REP(i,g.size()){

			REP(j,g[i].size()){

				printf("%d:(%d,%d)\n",i,g[i][j].src,g[i][j].dst);

			}

		}*/

		Edges ed;

		int ret = bipartiteMatching(g, n, ed);

		/*

		REP(i,ed.size()){

			printf("%d -> %d\n",ed[i].src,ed[i].dst);

		}

		*/

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

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3308267230839952x):
#include <iostream>

#include <vector>

#include <cstring>

using namespace std;



#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)

#define rep(i,n) REP(i,0,n)



vector<int> edge[1010];

int match[1010];

bool used[1010];



bool dfs(int v){

  used[v] = true;

  rep(i,edge[v].size()){

    int u = edge[v][i];

    int w = match[u];

    if( w<0 || !used[w]&&dfs(w) ){

      match[v] = u;

      match[u] = v;

      return true;

    }

  }

  return false;

}

int solve(int sz){

  int ret = 0;

  memset(match,-1,sizeof(match));

  rep(i,sz)if( match[i]<0 ){

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

    if( dfs(i) )ret++;

  }

  return ret;

}





int gcd(int x, int y){

  return y ? gcd(y,x%y) : x;

}



int main(){

  int n,m;

  int blue[500],red[500];



  while(cin>>n>>m, n|m){

    // init

    rep(i,n+m+1)edge[i].clear();



    

    rep(i,n)scanf("%d",&blue[i]);

    rep(i,m)scanf("%d",&red[i]);

    rep(i,n){

      rep(j,m){

        if( gcd(blue[i], red[j])!=1 ){

          edge[i].push_back(j+n);

          edge[j+n].push_back(i);

        }

      }

    }

    cout << solve(n+m) << endl;

  }

  return 0;

}