#include<iostream>
#include<vector>

using namespace std;

vector<int> blue;
vector<int> red;
vector<int> redpair;
vector<int> v;
vector<vector<int> >c;

int m = 0;
int n = 0;

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

bool match(int x){
    if(x == -1){
        return 1;
    }
    for(int i = 0;i < n;i++){
        if(c[x][i] == 1 && v[i] == 0){
            v[i] = 1;
            if(match(redpair[i])){
                redpair[i] = x;
                return 1;
            }
        }
    }
    return 0;
}


int main(){
    while(cin >> m >> n){
        if(m == 0 && n == 0){
            break;
        }
        blue.clear();
        red.clear();
        redpair.clear();
        v.clear();
        c.clear();
        for(int i = 0;i < m;i++){
            int tmp = 0;
            cin >> tmp;
            blue.push_back(tmp);
        }
        for(int i = 0;i < n;i++){
            int tmp = 0;
            cin >> tmp;
            red.push_back(tmp);
            redpair.push_back(-1);//-1??§?????¢??????????????¶????????¨???
            v.push_back(0);
        }
        for(int i = 0;i < m;i++){
            c.push_back(vector<int>());
            for(int j = 0;j < n;j++){
                c[i].push_back(gcd(blue[i],red[j]) != 1);
            }
        }
        int ans = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                v[j] = 0;
            }
            if(match(i)){ans++;}
        }
        cout << ans << endl;
    }
    return 0;
}