#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const ll INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct{template<class T> operator T(){T x;cin>>x;return x;}} IN;
struct before_main_function {
    before_main_function() {
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

template <typename T>
struct EdmondsKarp {
    struct Edge {
        int from;
        int to;
        T cap;
    };

    int size;
    vector<Edge> edge;
    vector<vector<int>> graph;

    EdmondsKarp(int size_) : size(size_) {
        graph.resize(size);
    }
    void add_edge(int from, int to, T cap) {
        graph[from].push_back(edge.size());
        edge.push_back(Edge{from, to, cap});
        graph[to].push_back(edge.size());
        edge.push_back(Edge{to, from, 0});
    }
    T max_flow(int s, int t) {
        auto get_reverse_edge = [](int e) {
            if (e % 2) return e - 1;
            else return e + 1;
        };

        T flow = 0;
        while (1) {
            queue<int> q;
            q.push(s);
            vector<int> from(size, -1);
            from[s] = -2;
            while (!q.empty()) {
                int v = q.front(); q.pop();
                if (v == t) break;
                for (auto &e : graph[v]) {
                    int w = edge[e].to;
                    if (edge[e].cap <= 0 || from[w] != -1) continue;
                    from[w] = e;
                    q.push(w);
                }
            }
            if (from[t] == -1) break;

            int cur = t;
            vector<int> arg_path;
            T bottleneck = 0;
            while (cur != s) {
                int e = from[cur];
                if (bottleneck == 0 || bottleneck > edge[e].cap) {
                    bottleneck = edge[e].cap;
                }
                arg_path.push_back(e);
                cur = edge[e].from;
            }
            for (auto &e : arg_path) {
                edge[e].cap -= bottleneck;
                edge[get_reverse_edge(e)].cap += bottleneck;
            }
            flow += bottleneck;
        }
        return flow;
    }
};

int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }

signed main() {
    while(1) {
        int n,m;
        cin>>n>>m;
        if(n==0 && m==0) break;
        vector<int> a(n),b(m);
        cin>>a>>b;
        EdmondsKarp<int> mf(n+m+2);
        REP(i,n) mf.add_edge(n+m,i,1);
        REP(i,m) mf.add_edge(i+n,n+m+1,1);
        REP(i,n) REP(j,m) if(gcd(a[i],b[j])>1) mf.add_edge(i,j+n,1);
        cout<<mf.max_flow(n+m,n+m+1)<<endl;
    }
    return 0;
}




Measured memory_bytes: 14540