#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct edge {int to,w,p;};
int n,m,k,used[1002],a,b,c,cnt,A[1002];
vector<edge> v[1002];
int dfs(int s,int t,int r){
    if(s==t)return r;
    used[s]=1;
    for(int i=0;i<v[s].size();i++){
        edge &u=v[s][i];
        if(used[u.to]==0&&u.w>0){
            int F=dfs(u.to,t,min(r,u.w));
            if(F>0){
                u.w-=F;v[u.to][u.p].w+=F;return F;
            }
        }
    }
    return 0;
}
int f(int a,int b){
    if(b==0)return a;
    return f(b,a%b);
}
int main(void){
    while(1){
    cin>>n>>m;
    if(n==0&&m==0)return 0;
    for(int i=0;i<1002;i++){
        A[i]=0;
        v[i]={};
    }
    for(int i=0;i<n;i++){
        cin>>A[i];
        a=1000,b=i;
        edge p={b,1,(int)v[b].size()};v[a].push_back(p);
        edge q={a,0,(int)v[a].size()-1};v[b].push_back(q);
    }
    for(int i=500;i<500+m;i++){
        cin>>A[i];
        a=i,b=1001;
        edge p={b,1,(int)v[b].size()};v[a].push_back(p);
        edge q={a,0,(int)v[a].size()-1};v[b].push_back(q);
    }
    for(int i=0;i<n;i++){
        for(int j=500;j<500+m;j++){
            if(f(A[i],A[j])>1){
                a=i,b=j;
                edge p={b,1,(int)v[b].size()};v[a].push_back(p);
                edge q={a,0,(int)v[a].size()-1};v[b].push_back(q);
            }
        }
    }
    int res=0;
    while(1){
        for(int i=0;i<1002;i++)used[i]=0;
        int P=dfs(1000,1001,1e9);
        if(P==0)break;
        res++;
    }
    cout<<res<<endl;
    }
}

