#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>

#define REP(i,n) for(i=0; i < (n); i++)
#define REPONE(i, n) for(i=1; i <= (n); i++)
#define LOOP(n) for(int loopCount=1; loopCount <= (n); loopCount++)
#define ITER(c) __typeof((c).begin())
#define EACH(c,it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define SZ(c) ((int) (c).size())
#define ALL(c) c.begin(), c.end()
#define SUM(c) accumulate(ALL(c), 0)
#define EXIST(c,v) (find(ALL(c), (v)) != (c).end())
#define PB push_back
#define MP make_pair

using namespace std;
static const double EPS = 1e-9;
static const double PI = 3.141592653589793238462643383279;
typedef long long ll;

template<typename T>
T FordFulkersonByMatrix(vector< vector<T> > &matrix, int source, int sink){
    int n = matrix.size();
    T maxCost = (T)0;
    vector< vector<T> > flowMat(n, vector<T>(n,0)), resMat = matrix;
    for(int i=0; i<n; i++)for(int j=0; j<n; j++)
        maxCost = max(maxCost,matrix[i][j]);

    while(1){
        stack<int> st;
        vector<int> parent(n,-1);
        st.push(source);
        while(!st.empty() && parent[sink] == -1){
            int tp = st.top(); st.pop();
            for(int i=0; i<n; i++){
                if(parent[i] == -1 && resMat[tp][i] > 0){
                    st.push(i);
                    parent[i] = tp;
                }
            }
        }
        if(parent[sink] == -1) break;
        T minCost = maxCost;
        for(int i=sink; i!=source; i = parent[i]){
            minCost = min(minCost, resMat[parent[i]][i]);
        }
        for(int i=sink; i!=source ; i = parent[i]){
            flowMat[parent[i]][i] += minCost;
            flowMat[i][parent[i]] -= minCost;
            resMat[parent[i]][i] -= minCost;
            resMat[i][parent[i]] += minCost;
        }
    }

    return accumulate(flowMat[source].begin(), flowMat[source].end(), (T)0);
}

int BipartiteMatchingByList(vector< vector<int> > &bigraph){
    int n=bigraph.size(), m;
    m = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<(int)bigraph[i].size(); j++){
            m = max(m, bigraph[i][j]);
        }
    }
    m++;
    vector< vector<int> > matrix(n+m+2, vector<int>(n+m+2,0));
    for(int i=0; i<n; i++){
        for(int j=0; j<(int)bigraph[i].size(); j++){
            matrix[i][n+bigraph[i][j]] = 1;
        }
    }
    for(int i=0; i<m; i++){
        matrix[n+i][n+m+1] = 1;
    }
    for(int j=0; j<n; j++){
        matrix[n+m][j] = 1;
    }

    return FordFulkersonByMatrix(matrix, n+m, n+m+1);
}

int main(){
    int m, n, i, j;
    int blues[502], reds[502];

    while(scanf("%d%d",&m,&n)){
        if(!(n||m))break;
        REP(i,m)scanf("%d",blues+i);
        REP(i,n)scanf("%d",reds+i);
        vector< vector<int> > bigraph(m);
        REP(i,m)REP(j,n)if(__gcd(blues[i], reds[j]) > 1)
            bigraph[i].PB(j);
        printf("%d\n", BipartiteMatchingByList(bigraph));
    }

    return 0;
}

Measured memory_bytes: 13000