#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
constexpr int IINF = INT_MAX;

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

vector<vector<edge> > G;
vector<bool> used;

void add_edge(int from, int to, int cap){
    G[from].emplace_back((edge){to, cap, int(G[to].size())});
    G[to].emplace_back((edge){from, 0, int(G[from].size())-1});
}

// 増加路の探索
int dfs(int v, int t, int f){
    if(v == t) return f;
    used[v] = true;
    for(auto &e : G[v]){
        if(!used[e.to] && e.cap > 0){
            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 s, int t){
    used.resize(G.size());
    int flow = 0;
    while(1){
        fill(used.begin(), used.end(), false);
        int f = dfs(s, t, IINF);
        if(f==0) break;
        flow += f;
    }
    return flow;
}

int gcd(int p, int q){
    if(q==0) return p;
    else return gcd(q, p%q);
}

int main() {
    int n, m;
    while(cin >> m >> n, m){
        G.clear();
        G.resize(m+n+2);
        vector<int> a(m), b(n);
        for(int i=0;i<m;i++) cin >> a[i];
        for(int i=0;i<n;i++) cin >> b[i];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(gcd(a[i], b[j]) > 1){
                    add_edge(i,j+m,1);
                }
            }
        }
        for(int i=0;i<m;i++){
            add_edge(n+m,i,1);
        }
        for(int i=0;i<n;i++){
            add_edge(i+m,n+m+1,1);
        }
        cout << max_flow(n+m, n+m+1) << endl;
    }
    return 0;
}

