#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define FIR first
#define SEC second
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

typedef int Flow;
struct Edge{
  int src;int dst;int rev;
  Flow cap;
  Edge(int s=0,int d=0,Flow c=0,int r=0):
  src(s),dst(d),cap(c),rev(r){}
};
using Graph = vector<vector<Edge>>;
Graph g;
bool used[100000];
int m,n;

void add(int src,int dst,int cap){
  g[src].emplace_back(src,dst,cap,g[dst].size());
  g[dst].emplace_back(dst,src,0,g[src].size()-1);
}
int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v]=true;
  REP(i,g[v].size()){
    Edge &e=g[v][i];
    if(!used[e.dst]&&e.cap>0){
      int d=dfs(e.dst,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        g[e.dst][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}
int maximum_flow(int s,int t){
  int flow=0;
  for(;;){
    fill(used,used+1111,0);
    int f=dfs(s,t,INF);
    if(!f)return flow;
    flow+=f;
  }
}

int gcd(int a,int b){
  if(a<b)swap(a,b);
  if(b==0)return a;
  return gcd(b,a%b);
}

signed main(){
  while(cin>>m>>n,m){
    g=Graph(1111);

    vector<pair<int,int>> B(m),R(n);
    REP(i,m){
      int b;
      cin>>b;
      B[i]=MP(b,i+1);
    }
    REP(i,n){
      int r;
      cin>>r;
      R[i]=MP(r,i+1+m);
    }
    REP(i,m)add(0,i+1,1);
    REP(i,n)add(m+i+1,n+m+1,1);

    REP(i,m){
      REP(j,n){
        if(gcd(B[i].FIR,R[j].FIR)>1){
          add(B[i].SEC,R[j].SEC,1);
        }
      }
    }
    cout<<maximum_flow(0,n+m+1)<<endl;
  }

  return 0;
}