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

#include <sstream>

#include <string>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cassert>



using namespace std;



#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)

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

#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)



template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }



typedef long long ll;

const int INF = 100000000;

const double EPS = 1e-8;

const int MOD = 1000000007;

struct edge{

  int to, cap, rev;

  edge(){}

  edge(int to, int cap, int rev):

    to(to), cap(cap), rev(rev) {}

};

typedef vector<edge> edges;

int gcd(int m,int n){

  return (m%n)?gcd(n, m%n):n;

}

void add_edge(vector<edges>& g, 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));

}

bool used[1002];

int dfs(vector<edges>& g, int u, int end, int f){

  if(u == end) return f;

  used[u] = true;

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

    edge& e = g[u][i];

    if(used[e.to] || e.cap <= 0) continue;

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

    if(t > 0){

      e.cap -= t;

      g[e.to][e.rev].cap += t;

      return t;

    }

  }

  return 0;

}

int maxflow(vector<edges>& g, int s, int e){

  int res = 0;

  while(true){

    memset(used, 0, sizeof(used));

    int f = dfs(g, s, e, 1);

    if(f == 0) return res;

    else res += f;

  }

  return -1;

}



int main(){

  int m,n;

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

    vector<int> v1(m);

    vector<int> v2(n);

    REP(i,m)cin>>v1[i];

    REP(i,n)cin>>v2[i];

    const int start = m + n;

    const int end = m + n + 1;;

    vector<edges> graph(end + 1);

    REP(i,m)add_edge(graph, start, i, 1);

    REP(i,n)add_edge(graph, m + i, end, 1);

    REP(i,m)REP(j,n)if(gcd(v1[i],v2[j])!=1){

      add_edge(graph, i, m + j, 1);

    }

    cout<<maxflow(graph,start,end)<<endl;

  }

  return 0;

}

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

#include <sstream>

#include <string>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cassert>



using namespace std;



#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)

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

#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)



template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }

inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }



typedef long long ll;

const int INF = 100000000;

const double EPS = 1e-8;

const int MOD = 1000000007;

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};

int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

typedef vector<int> Node;

typedef vector<Node> Graph;

int V1, V2;

Graph G;

int dist[1002];

int match[1002];

const int NIL = 1001;

bool BFS(){

  queue<int> que;

  REP(v, V1){

    if(match[v] == NIL){

      dist[v] = 0;

      que.push(v);

    }else{

      dist[v] = INF;

    }

  }

  dist[NIL] = INF;

  while(!que.empty()){

    int v = que.front(); que.pop();

    if(dist[v] < dist[NIL]){

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

        int u = G[v][i];

        if(dist[match[u]] == INF){

          dist[match[u]] = dist[v] + 1;

          que.push(match[u]);

        }

      }

    }

  }

  return dist[NIL] != INF;

}



bool DFS(int v){

  if(v != NIL){

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

      int u = G[v][i];

      if(dist[match[u]] == dist[v] + 1 && DFS(match[u])){

        match[u] = v;

        match[v] = u;

        return true;

      }

    }

    dist[v] = INF;

    return false;

  }

  return true;

}



int Hopcroft_Karp(){

  REP(v, G.size()) match[v] = NIL;

  int matching = 0;

  while(BFS()){

    REP(v, V1){

      if(match[v] == NIL && DFS(v)){

        matching ++;

      }

    }

  }

  return matching;

}

int main(){

  while(scanf("%d %d", &V1, &V2) && (V1 != 0 || V2 != 0)){

    G = Graph(V1 + V2);

    static int blue[500];

    static int red[500];

    REP(i, V1) scanf("%d", blue + i);

    REP(i, V2) scanf("%d", red + i);

    REP(u, V1) REP(v, V2){

      if(__gcd(blue[u], red[v]) != 1) {

        G[u].push_back(V1 + v);

        //G[V1 + v].push_back(u);

      }

    }

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

  }

  return 0;

}