#include <iostream>
using namespace std;

int m, n;
int blue[505];
int red[505];

bool bluematch[505];
int redpair[505];

int path[505][505];

int gcd(int a, int b)
{
    int m;
    
    while(1){
        m = a%b;
        if(m==0)
            return b;
        a = b;
        b = m;
    }
    return 1;
}

bool match(int x){
    if(x<0) return true;
    
    if(bluematch[x]){
        return false;
    }
    bluematch[x]=true;
    
    for(int y=0; y<n; y++){
        if(!path[x][y]) continue;
        if(match(redpair[y])){
            redpair[y]=x;
            return true;
        }
    }
    
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    
    int i, j, cnt;
    while(1){
        cin >> m >> n;
        if(m==0)
            return 0;
        
        for(i=0;i<m;i++){
            cin >> blue[i];
        }
        
        for(i=0;i<n;i++){
            cin >> red[i];
        }
        
        for(i=0; i<m; i++){
            for(j=0; j<n; j++){
                if(gcd(blue[i],red[j])!=1){
                    path[i][j]=1;
                }
                else{
                    path[i][j]=0;
                }
            }
        }
        
        fill(redpair, redpair+n, -1);
        cnt=0;
        for(i=0; i<m; i++){
            fill(bluematch, bluematch+m, 0);
            if(match(i)){
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    
    return 0;
}