#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)
int const inf = 1<<29;

struct MCF {
    typedef int Weight;
    typedef int Capacity;
    struct Edge;
    int n;
    vector<vector<Edge> > g;
    vector<int> level, iter;

    struct Edge {
        int dst;
        Capacity cap, cap_orig;
        int revEdge;
        bool isRev;
        Edge(int dst, Capacity cap, int revEdge, bool isRev)
        :dst(dst), cap(cap), cap_orig(cap), revEdge(revEdge), isRev(isRev) {}
    };

    MCF(int n_)
    : n(n_), g(vector<vector<Edge> >(n_)), level(n_), iter(n_) {}

    void add_edge(int src, int dst, Capacity cap) {
        g[src].push_back(Edge(dst, cap, g[dst].size(), false));
        g[dst].push_back(Edge(src, 0, g[src].size() - 1, true));
    }

    void bfs(int s) {
        fill(all(level), -1);
        queue<Weight> q;
        level[s] = 0;
        q.push(s);
        while (q.size()) {
            int v = q.front(); q.pop();
            for(int i = 0; i < (int)g[v].size(); i++){
                Edge& e = g[v][i];
                if (e.cap > 0 && level[e.dst] < 0) {
                    level[e.dst] = level[v] + 1;
                    q.push(e.dst);
                }
            }
        }
    }

    Capacity dfs(int v, int t, int f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < (int)g[v].size(); i++) {
            Edge &e = g[v][i];
            if (e.cap > 0 && level[v] < level[e.dst]) {
                int d = dfs(e.dst, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.dst][e.revEdge].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    // src->dstへの最大フローを流す
    Capacity max_flow(int src, int dst) {
        int flow = 0;
        while(1){
            bfs(src);
            if (level[dst] < 0) return flow;
            fill(all(iter), 0);
            int f;
            while ((f = dfs(src, dst, inf)) > 0) {
                flow += f;
            }
        }
    }

    // 現在の容量を表示
    // フローを流した分だけ容量が減る実装になっている
    void view(){
        for(int i=0;i<g.size();i++){
            for(int j=0;j<g[i].size();j++){
                Edge & e=g[i][j];
                if(!e.isRev) printf("%3d->%3d (flow:%d)\n", i, e.dst, e.cap);
            }
        }
    }

    // 流れたフロー=元々の容量-現在の容量を表示
    void view_flow(){
        for(int i=0;i<g.size();i++){
            for(int j=0;j<g[i].size();j++)if(!g[i][j].isRev){
                Edge& e = g[i][j];
                printf("%3d->%3d (flow:%d)\n", i, e.dst, e.cap_orig - e.cap);
            }
        }
    }
};

int main(){
    int n,m;
    while(cin>>n>>m && n|m){
        vector<int> a(n), b(m);
        rep(i,n)cin>>a[i];
        rep(i,m)cin>>b[i];
        MCF mcf(n+m+2);
        int s=n+m, t=n+m+1;
        rep(i,m)mcf.add_edge(i+n,t,1);
        rep(i,n){
            mcf.add_edge(s,i,1);
            rep(j,m)if(__gcd(a[i],b[j])!=1)mcf.add_edge(i,n+j,1);
        }
        cout << mcf.max_flow(s,t) << endl;
    }
}

Measured memory_bytes: 8316