#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cstdio>
#include <stack>

using namespace std;

int gcd(int m, int n) {
    if(m < n) return gcd(n, m);
    while(n != 0) {
        int tmp = m % n;
        m = n;
        n = tmp;
    }
    return m;
}

//flow_vÍÚ±zñ
//pairÍ<s«æ, RXg>
int maxflow(const vector<vector<pair<int, int> > > &flow_v, int s, int g) {
    int size = flow_v.size();
    //×ÚsñÉÏ·
    //Å©ç×ÚsñnµÈç±±Í¢çÈ¢
    /*****½¾µAtûüÉÌRXgªüÁÄ¢é©ÍvmF*****/
    vector<vector<int> > capacity(size, vector<int>(size, 0));
    for(int i = 0; i < size; ++i) {
        for(int j = 0; j < flow_v[i].size(); ++j) {
            int to = flow_v[i][j].first;
            int cost = flow_v[i][j].second;
            capacity[i][to] = cost;
        }
    }
    vector<vector<int> > flow(size, vector<int>(size, 0));

    int ans = 0;
    while(true) {
        //DæTõÅaugument flowðÝÂ¯é
        queue<int> q;
        vector<int> prev(size, -1);
        prev[s] = s;
        q.push(s);
        while(!q.empty()) {
            int n = q.front();
            q.pop();
            for(int i = 0; i < size; ++i) {
                if(capacity[n][i]-flow[n][i] <= 0) continue;
                if(prev[i] != -1) continue;
                prev[i] = n;
                q.push(i);
                if(i == g) goto endloop;
            }
        }
endloop:
        if(prev[g] == -1) break;
        int res = INT_MAX;
        for(int i = g; prev[i] != i; i = prev[i]) {
            res = min(res, capacity[prev[i]][i]-flow[prev[i]][i]);
        }
        for(int i = g; prev[i] != i; i = prev[i]) {
            flow[prev[i]][i] += res;
            flow[i][prev[i]] -= res;
        }
        ans += res;
    }
    return ans;
}

//E¶©çt[ª¬êÄ­é½ßAE©ç¶Ös­ÌÍùÉ¶ÝµÄ¢ét[Ìt¬ÌÝ
//EæÁÄAE©ç¶ÖsÁÄA»±ÅtrueÅ~Üé±ÆÍ è¾È¢
//@i¶¸_ÍEÖÌmatchToª èA©Â»¿çÖÍißÈ¢ÌÅK¸falseÉÈéj
//E±ÌASYÅÍA
//@nF¶¸_
//@g[n][i]FE¸_
//@matchTo[g[n][i]]F¶¸_or-1
//@ª¬§µÄ¢é
bool bm_helper(const vector<vector<int> > &g, vector<int> &matchTo, int n, vector<bool> &used) {
    if(n == -1) return true;

    for(int i = 0; i < g[n].size(); ++i) {
        if(used[g[n][i]]) continue;
        //Ç¤¹±Ì¸_ÉßÁÄ«Äàaugment pathÍ©Â©éí¯È¢ÌÅ³µÈ­Äæ¢
        used[g[n][i]] = true;
        if(bm_helper(g, matchTo, matchTo[g[n][i]], used)) {
            matchTo[n] = g[n][i];
            matchTo[g[n][i]] = n;
            return true;
        }
    }
    return false;
}

//gÍÚ±zñiN«¾µAz¢ÝÍ¢çÈ¢j
//LÍ}b`OÌ¶¤¸_Ì«EiL¢ª¶¤j
int bipartiteMatch(const vector<vector<int> > &g, int L) {
    int size = g.size();
    vector<int> match(size, -1);
    //[³DæÅaugment pathð©Â¯é
    //Ford FurlkersonÌASYB
    //êñÌ¸ÅK¸t[ª1Í¦é½ßA
    //¶¤ðSÄÈßs­µ½ ÆÍðÉÈÁÄ¢é
    int cnt = 0;
    for(int i = 0; i < L; ++i) {
        vector<bool> used(g.size(), false);
        if(bm_helper(g, match, i, used)) ++cnt; //augment pathª©Â©é->t[ª1¦é
    }
    return cnt;
}

int main() {
    while(true) {
        int m, n;
        cin >> m >> n;
        if(!m && !n) break;

        vector<int> cards(m+n);
        //vector<vector<pair<int, int> > > graph(m+n+2);
        vector<vector<int> > graph(m+n);
        //For maxflow
        /*
        for(int i = 0; i < m; ++i) {
            //cin >> cards[i];
            scanf("%d", &cards[i]);
            graph[m+n].push_back(make_pair(i, 1)); //Start node
        }
        for(int i = m; i < m+n; ++i) {
            scanf("%d", &cards[i]);
            for(int j = 0; j < m; ++j) {
                if(gcd(cards[i], cards[j]) > 1) {
                    graph[j].push_back(make_pair(i, 1));
                }
            }
            graph[i].push_back(make_pair(m+n+1, 1)); //Goal node
        }
        cout << maxflow(graph, m+n, m+n+1) << endl;
        */
    
        //For bipartiteMatch
        for(int i = 0; i < m; ++i) {
            scanf("%d", &cards[i]);
        }
        for(int i = m; i < m+n; ++i) {
            scanf("%d", &cards[i]);
            for(int j = 0; j < m; ++j) {
                if(gcd(cards[i], cards[j]) > 1) {
                    graph[j].push_back(i);
                }
            }
        }
        cout << bipartiteMatch(graph, m) << endl;
    }
    return 0;
}

Measured memory_bytes: 1760