#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;

//Dinic
//最大流を高速に求めることが出来ます
//二部マッチングにも使ってください
class Dinic{
public:

    //引数はありうる頂点の最大の数を入れてください
    explicit Dinic(int v):vertex(static_cast<unsigned int>(v)){
        G.resize(vertex+10);
    }

    //頂点fromからtoへの流せる量の最大がcapのとき、add_edge(int from,int to,ll cap)
    //
    //二部マッチングのときは、capは1にしてください
    //二部マッチングのとき、意図的に、与えられる頂点以外に２つ頂点を作ってください
    //それをs,tとしてsからtへの最大流を求めてください
    void add_edge(int from,int to,ll cap){
        G[from].push_back((edge){to, cap, static_cast<int>(G[to].size())});
        G[to].push_back((edge){from, 0, static_cast<int>(G[from].size() - 1)});
    }

    ll max_flow(int s,int t){//s->start , t->end
        ll flow=0;
        for(;;){
            bfs(s);
            if(level[t]<0)return flow;
            iter.clear();
            iter.resize(vertex+10,0);
            ll f;
            while((f=dfs(s,t,INF))>0)flow+=f;
        }
    }
private:
    unsigned int vertex;
    struct edge{
        int to;
        ll cap;
        int rev;
    };
    vector<vector<edge> > G;
    vector<int> level;
    vector<int> iter;
    ll INF=(ll)1e16;
    void bfs(int start){
        level.clear();
        level.resize(vertex+10,-1);
        queue<int> q;
        q.push(start);
        level[start]=0;
        while(!q.empty()){
            int now=q.front();
            q.pop();
            for(int i=0;i<(int)G[now].size();i++) {
                if(G[now][i].cap>0 && level[G[now][i].to]<0){
                    level[G[now][i].to]=level[now]+1;
                    q.push(G[now][i].to);
                }
            }
        }
    }
    ll dfs(int now,int t,ll f){
        if(now==t)return f;
        for(int &i=iter[now];i<(int)G[now].size();i++){
            edge &e=G[now][i];
            if(e.cap>0 && level[now]<level[e.to]){
                ll d=dfs(e.to,t,min(f,e.cap));
                if(d>0){
                    e.cap-=d;
                    G[e.to][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return 0;
    }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  while(cin>>n>>m,n){
    int blue[501],red[501];
    for(int i=0;i<n;i++){
      cin>>blue[i];
    }
    for(int i=0;i<m;i++){
      cin>>red[i];
    }
    Dinic d(1011);
    int s=n+m;
    int t=s+1;
    for(int i=0;i<n;i++){
      d.add_edge(s,i,1);
    }
    for(int i=0;i<m;i++){
      d.add_edge(n+i,t,1);
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(__gcd(blue[i],red[j])!=1){
          d.add_edge(i,n+j,1);
        }
      }
    }
    ll ans=d.max_flow(s,t);
    cout<<ans<<endl;
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}







Measured memory_bytes: 11396