// Slower C++ solution:
#include<bits/stdc++.h>

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

#define pb push_back

 

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

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

#define REP(i,n) for (int i=0;i<(n);i++)

#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

 

#define MAX_N 500

#define MAX_K 500

#define MAX_V 1002

#define INF 1000000000

 

 

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

vector<edge> G[MAX_V];

bool used[MAX_V]; 

int V;

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

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

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

}

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

    if (v == t) return f;

    used[v] = true;

    for (int i = 0; i < G[v].size(); i++) {

        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;

    for (;;) {

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

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

        if (f == 0) return flow;

        flow += f;

    }

}

void resetG(int ver){

    V = ver;

    REP(i,V)

        G[i].clear();

}

 

int N, K;

bool can[MAX_N][MAX_K];

void solve() {

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

    for (int i = 0; i < N; i++) {

        add_edge(s, i, 1);

    }

    for (int i = 0; i < K; i++) {

        add_edge(N + i, t, 1);

    }

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < K; j++) {

            if (can[i][j]) {

                add_edge(i, N + j, 1);

            }

        }

    }

    printf("%d\n",max_flow(s,t));

}

 

int gcd(int a,int b){

    if(a < b){

        int c = a;

        a = b;

        b = c;

    }

    if(a % b == 0)

        return b;

    return gcd(b,a % b);

}

 

int inb[500],inr[500];

 

bool input(){

    scanf("%d%d",&N,&K);

    if(N == 0 && K == 0)

        return false;

    REP(i,N)

        scanf("%d",&inb[i]);

    REP(i,K)

        scanf("%d",&inr[i]);

 

    memset(can,false,sizeof(can));

    REP(i,N){

        REP(j,K){

            if(gcd(inb[i],inr[j]) > 1)

                can[i][j] = true;

        }

    }

    resetG(N + K + 2);

    return true;

}

 

int main(){

    while(input()){

        solve();

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.237264038589951x):
#include<bits/stdc++.h>

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

#define pb push_back



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

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

#define REP(i,n) for (int i=0;i<(n);i++)

#define RREP(i,n) for (int i=(n)-1;i>=0;i--)



#define MAX_N 500

#define MAX_K 500

#define MAX_V 1002

#define INF 1000000000



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

vector<edge> G[MAX_V]; // ??°???????????£??\???????????¨???

int V;

int level[MAX_V]; // s??????????????¢

int iter[MAX_V]; // ???????????§??????????????£??????

// from??????to??????????????????cap???????????°?????????????????????

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

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

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

}

// s????????????????????¢???BFS??§?¨??????????

void bfs(int s) {

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

    queue<int> que;

    level[s] = 0;

    que.push(s);

    while (!que.empty()) {

        int v = que.front(); que.pop();

        for (int i = 0; i < G[v].size(); i++) {

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

            if (e.cap > 0 && level[e.to] < 0) {

                level[e.to] = level[v] + 1;

                que.push(e.to);

            }

        }

    }

}

// ?¢?????????????DFS??§??¢???

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

    if (v == t) return f;

    for (int &i = iter[v]; i < G[v].size(); i++) {

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

        if (e.cap > 0 && level[v] < level[e.to]) {

            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;

}

// s??????t???????????§???????±???????

int max_flow(int s, int t) {

    int flow = 0;

    for (;;) {

        bfs(s);

        if (level[t] < 0) return flow;

        memset(iter, 0, sizeof(iter));

        int f;

        while ((f = dfs(s, t, INF)) > 0) {

            flow += f;

        }

    }

}

void resetG(int ver){

    V = ver;

    REP(i,V)

        G[i].clear();

}



int N, K;

bool can[MAX_N][MAX_K];

void solve() {

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

    for (int i = 0; i < N; i++) {

        add_edge(s, i, 1);

    }

    for (int i = 0; i < K; i++) {

        add_edge(N + i, t, 1);

    }

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < K; j++) {

            if (can[i][j]) {

                add_edge(i, N + j, 1);

            }

        }

    }

    printf("%d\n",max_flow(s,t));

}



int gcd(int a,int b){

    if(a < b){

        int c = a;

        a = b;

        b = c;

    }

    if(a % b == 0)

        return b;

    return gcd(b,a % b);

}



int inb[500],inr[500];



bool input(){

    scanf("%d%d",&N,&K);

    if(N == 0 && K == 0)

        return false;

    REP(i,N)

        scanf("%d",&inb[i]);

    REP(i,K)

        scanf("%d",&inr[i]);



    memset(can,false,sizeof(can));

    REP(i,N){

        REP(j,K){

            if(gcd(inb[i],inr[j]) > 1)

                can[i][j] = true;

        }

    }

    resetG(N + K + 2);

    return true;

}



int main(){

    while(input()){

        solve();

    }

    return 0;

}