#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;

struct edge
{
    int to,cap,rev;
};

class BM {
private:
    vector<vector<edge> > G;
    vector<int> level;
    vector<int> iter;
    int u,v;

public:
    BM(vector<int> a,vector<int> b){
        u = (int)a.size(),v = (int)b.size();
        G.resize(u+v+2);
        level.resize(u+v+2);
        iter.resize(u+v+2);
        rep(i,a.size()){
            init_edge(0,i+1);
        }
        rep(i,b.size()){
            init_edge(u+i+1,u+v+1);
        }
    }

    void init_edge(int from,int to)
    {
        G[from].pb((edge){to,1,G[to].size()});
    	G[to].pb((edge){from,0,G[from].size()-1});
    }

    void add_edge(int from,int to)
    {
        from += 1,to += u+1;
    	G[from].pb((edge){to,INF,G[to].size()});
    	G[to].pb((edge){from,0,G[from].size()-1});
    }

    void bfs(int s)
    {
        fill(all(level),-1);
    	queue<int> que;
    	level[s] = 0;
    	que.push(s);
    	while(!que.empty()){
    		int v = que.front();
    		que.pop();
    		rep(i,G[v].size()){
    			edge &e = G[v][i];
    			if(e.cap > 0 && level[e.to] < 0){
    				level[e.to] = level[v] + 1;
    				que.push(e.to);
    			}
    		}
    	}
    }

    int dfs(int v,int t,int f)
    {
    	if(v==t){
    		return f;
    	}
    	for(int &i = iter[v];i<G[v].size();i++){
    		edge &e = G[v][i];
    		if(e.cap > 0 && level[v] < level[e.to]){
    			int 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 max_flow()
    {
    	int flow = 0;
        int s=0,t=u+v+1;
    	for(;;){
    		bfs(s);
    		if(level[t]<0){
    			return flow;
    		}
            fill(all(iter),0);
    		int f;
    		while((f=dfs(s,t,INF)) > 0){
    			flow += f;
    		}
    	}
    }
};

int gcd(int x,int y)
{
    if(x % y == 0){
        return y;
    }else{
        return gcd(y,x%y);
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(1){
        int m,n;
        cin >> m >> n;
        if(m == 0 && n == 0){
            break;
        }
        vector<int> a(m),b(n);
        rep(i,m){
            cin >> a[i];
        }
        rep(i,n){
            cin >> b[i];
        }
        BM bm(a,b);
        rep(i,m){
            rep(j,n){
                if(gcd(a[i],b[j]) > 1){
                    bm.add_edge(i,j);
                }
            }
        }
        cout << bm.max_flow() << endl;
    }
    return 0;
}

Measured memory_bytes: 7432