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

#include<algorithm>

#include<vector>

using namespace std;



class bipartite_matching{

private:

  int V;

  vector< vector< int > > info;

  vector< int > match;

  vector< bool > used;

public:

  bipartite_matching(int V_size):V(V_size){

    info.resize(V_size);

    used.resize(V_size);

    match.resize(V_size);

  };

  void add_edge( int u, int v){

    info[u].push_back(v);

    info[v].push_back(u);

  }

  bool dfs( int v){

    used[v] = true;

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

      int u = info[v][i], w = match[u];

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

        match[v] = u, match[u] = v;

        return true;

      }

    }

    return false;

  }

  int run(){

    match.assign(V,-1);

    int ret = 0;

    for(int i = 0; i < V; i++){

      if(match[i] < 0){

        used.assign(V,false);

        if(dfs(i)) ret++;

      }

    }

    return ret;

  }

};



int main(){

  int m, n, b[500], r[500];

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

    bipartite_matching bm(n + m);

    for(int i = 0; i < m; i++){

      cin >> b[i];

    }

    for(int i = 0; i < n; i++){

      cin >> r[i];

    }

    for(int i = 0; i < m; i++){

      for(int j = 0; j < n; j++){

        if(__gcd(b[i],r[j]) > 1) bm.add_edge( i, m + j);

      }

    }

    cout << bm.run() << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 1.2113324737833304x):
#include<bits/stdc++.h>



using namespace std;



struct Bipartite_Matching

{

  vector< vector< int > > graph;

  vector< int > dist, match;

  vector< bool > used, vv;



  Bipartite_Matching(int n, int m)

  {

    graph.resize(n);

    match.assign(m, -1);

    used.assign(n, false);

  }



  void add_edge(int u, int v)

  {

    graph[u].push_back(v);

  }



  void bfs()

  {

    dist.assign(graph.size(), -1);

    queue< int > que;

    for(int i = 0; i < graph.size(); i++) {

      if(!used[i]) {

        que.emplace(i);

        dist[i] = 0;

      }

    }



    while(!que.empty()) {

      int a = que.front();

      que.pop();

      for(auto &b : graph[a]) {

        int c = match[b];

        if(c >= 0 && dist[c] == -1) {

          dist[c] = dist[a] + 1;

          que.emplace(c);

        }

      }

    }

  }



  bool dfs(int a)

  {

    vv[a] = true;

    for(auto &b : graph[a]) {

      int c = match[b];

      if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {

        match[b] = a;

        used[a] = true;

        return (true);

      }

    }

    return (false);

  }



  int bipartite_matching()

  {

    int ret = 0;

    while(true) {

      bfs();

      vv.assign(graph.size(), false);

      int flow = 0;

      for(int i = 0; i < graph.size(); i++) {

        if(!used[i] && dfs(i)) ++flow;

      }

      if(flow == 0) return (ret);

      ret += flow;

    }

  }

};



int main()

{

  int M, N, B[500], R[500];

  while(scanf("%d %d", &M, &N), M) {

    Bipartite_Matching flow(M, N);

    for(int i = 0; i < M; i++) scanf("%d", &B[i]);

    for(int i = 0; i < N; i++) scanf("%d", &R[i]);

    for(int i = 0; i < M; i++) {

      for(int j = 0; j < N; j++) {

        if(__gcd(B[i], R[j]) > 1) flow.add_edge(i, j);

      }

    }

    printf("%d\n", flow.bipartite_matching());

  }

}