// Slower C++ solution:
#include <algorithm>

#include <bitset>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <stack>

#include <string>

#include <vector>



#define rep(i,a) for(int i = 0;i < (a); i++)

#define repi(i,a,b) for(int i = (a); i < (b); i++)

#define repd(i,a,b) for(int i = (a); i >= (b); i--)

#define repit(i,a) for(__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)

#define all(u) (u).begin(),(u).end()

#define rall(u) (u).rbegin(),(u).rend()

#define UNIQUE(u) (u).erase(unique(all(u)),(u).end())

#define pb push_back

#define mp make_pair

#define INF 1e9

#define EPS 1e-9

#define PI acos(-1.0)

#define MAX 2000

using namespace std;



typedef long long ll;

typedef vector<int> vi;

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

vector<edge> G[MAX];

bool used[MAX];



void add_edge(int from, int to, int cap){

    G[from].pb((edge){to, cap, G[to].size()});

    G[to].pb((edge){from, 0, G[from].size() - 1});

}



int dfs(int v, int t, int f){

    if(v == t) return f;

    used[v] = true;

    rep(i, G[v].size()){

        edge &e = G[v][i];

        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){

    int flow = 0;

    while(1){

        memset(used, 0, sizeof(used));

        int f = dfs(s, t, INF);

        if(f == 0) return flow;

        flow += f;

    }

}

int N, K;

int main() {

    while(cin >> N >> K, N||K){

        vector<int> b(N), r(K);

        rep(i, N) cin >> b[i];

        rep(i, K) cin >> r[i];

        rep(i, MAX) G[i].clear();

        int s = N+K, t = s+1;

        rep(i, N) add_edge(s, i, 1);

        rep(i, K) add_edge(N+i, t, 1);

        rep(i, N) rep(j, K) if(__gcd(b[i], r[j]) > 1) add_edge(i, N+j, 1);

        cout << max_flow(s, t) << endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4775499878468912x):
#include <algorithm>

#include <bitset>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <stack>

#include <string>

#include <vector>



#define repi(i,a,b) for(int i=(a);i<(b);i++)

#define rep(i,a) repi(i,0,a)

#define repd(i,a,b) for(int i=(a);i>=(b);i--)

#define repit(i,a) for(__typeof((a).begin()) i=(a).begin();i!=(a).end();i++)



#define all(u) (u).begin(),(u).end()

#define rall(u) (u).rbegin(),(u).rend()

#define UNIQUE(u) (u).erase(unique(all(u)),(u).end())



#define pb push_back

#define mp make_pair

#define INF 1e9

#define EPS 1e-9

#define PI acos(-1.0)



using namespace std;



typedef long long ll;

typedef vector<int> vi;



const int MAX_V = 1024;

int  V;

vector<int> G[MAX_V];

int match[MAX_V];

bool used[MAX_V];



void add_edge(int u, int v){

    G[u].push_back(v);

    G[v].push_back(u);

}



bool dfs(int v){

    used[v] = 1;

    rep(i,G[v].size()){

        int u = G[v][i], w = match[u];

        if(w < 0 || !used[w] && dfs(w)){

            match[v] = u;

            match[u] = v;

            return 1;

        }

    }

    return 0;

}



int bi_matching(){

    int res = 0;

    memset(match, -1, sizeof(match));

    rep(v,V) if(match[v] < 0){

        memset(used, 0, sizeof(used));

        if(dfs(v)) res++;

    }

    return res;

}



int b[512], r[512], n, m;



int solve(){

    rep(i,m) rep(j,n) if(__gcd(b[i],r[j]) > 1) add_edge(i,m+j);

        

    return bi_matching();

}



int main()

{

    while(cin >> m >> n, m or n){

        rep(i,m) cin >> b[i];

        rep(i,n) cin >> r[i];

        V = m+n;

        rep(i,MAX_V) G[i].clear();

        cout << solve() << endl;

    }

    return 0;

}