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

#include <vector>

using namespace std;



// ?????§????§£????????????????????????

class MaxFlow{

private:

  // edge: ??£??\??????????????? (to: ?????????, cap: ??????, rev: ???????????????(G[to][rev]?????????))

  // G: ??£??\?????????, used: ?????¨???????????????

  struct edge{

    int to, cap, rev;

    edge(int to_, int cap_, int rev_){ to = to_; cap = cap_; rev = rev_; }

  };

  vector<vector<edge> > G;

  vector<bool> used;

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

public:

  // ?????????????????????

  MaxFlow(int size){

    G = vector<vector<edge> >(size);

    used = vector<bool>(size);

  }

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

  int flow(int s, int t);

};



// ????????????

void MaxFlow::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));

}



// ??±???????????¢?´¢??§?¢???????????????¢???

// v: ?????¨??°???, t: ??????, f: ???????????????

int MaxFlow::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){

      // ????????????????????°??????dfs

      int d = dfs(e.to, t, ((f < e.cap) ? f : e.cap));

      // ??????1ml??§??????????????????????????????

      if(d > 0){

        e.cap -= d;

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

        return d;

      }

    }

  }

  

  return 0;

}



// s??????t?????§????????§???????±???????

int MaxFlow::flow(int s, int t){

  int flow = 0;

  while(true){

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

      used[i] = false;

    int f = dfs(s, t, 1e9);

    if(f == 0){ return flow; }

    flow += f;

  }

}



int gcd(int a, int b){

  if(b == 0){ return a; }

  return gcd(b, a % b);

}





int main(void){

  while(true){

    int m, n;

    cin >> m >> n;

    if(m == 0 && n == 0){ break; }



    // ??????????????£?¨?

    MaxFlow f(m + n + 2);



    // ???????????????????????????????????????

    vector<int> b(m);

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

      cin >> b[i];

      // ?§?????????????????????????????????°???

      f.add_edge(0, 1 + i, 1);

    }



    // ???????????????????????????????????????

    int r;

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

      cin >> r;

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

        // ???????????§??¬?´???°???1????????§???????????°?????????????????????????????????????????°???

        if(gcd(r, b[j]) > 1){ f.add_edge(1 + j, 1 + m + i, 1); }

      }

      // ???????????????????????????????????°???

      f.add_edge(1 + m + i, 1 + m + n, 1);

    }



    // ?????§???????±?????????????

    cout << f.flow(0, 1 + m + n) << endl;

  }

  

  return 0;

}

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

#include <vector>

using namespace std;



// ?¢?????????????DFS??§??¢???

bool dfs(int v, vector<vector<int> >& G, vector<int>& match, vector<bool>& used){

  // ??????????????¨???????????????

  used[v] = true;

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

    int u = G[v][i];

    int w = match[u];

    // w?????????????????¨????????? or (w???????????¨ && ?????????????°´??????????????´???)

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

      // v??¨u??????????????????

      match[v] = u;

      match[u] = v;

      return true;

    }

  }

  return false;

}



// ?????¨??°??????????????§??????????????°????±???????

// ?????????: (??????????????°??°, ??????????????°?????????)

pair<int, vector<int> > BipartiteMatching(vector<vector<int> >& G){

  int V = G.size();

  int res = 0;

  vector<int> match(V, -1);

  // ?????????????????????

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

    // v???????????????????????£???????????????????????°??§??????????????? 

    if(match[v] < 0){

      vector<bool> used(V, false);

      if(dfs(v, G, match, used)){ res++; }

    }

  }

  return make_pair(res, match);

}





int gcd(int a, int b){

  if(b == 0){ return a; }

  return gcd(b, a % b);

}





int main(void){

  while(true){

    int m, n;

    cin >> m >> n;

    if(m == 0 && n == 0){ break; }

    vector<int> b(m), r(n);

    for(int i = 0; i < m; i++){ cin >> b[i]; }

    for(int i = 0; i < n; i++){ cin >> r[i]; }



    vector<vector<int> > adjlist(m + n);

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

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

        if(gcd(b[i], r[j]) > 1){

          adjlist[i].push_back(m + j);

          adjlist[m + j].push_back(i);

        }        

      }

    }



    int result = BipartiteMatching(adjlist).first;

    cout << result << endl;

  }



  return 0;

}