#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) begin(c), end(c)
#define range(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) range(i,0,b)
#define rangei(i,a,b) for(ll a=a;i<=ll(b);i++)
#define repi(i,b) rangei(i,1,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator << (ostream &os, vector<T> const &);
template<int n, class...T>
typename enable_if<(n>=sizeof...(T))>::type
_ot(ostream &, tuple<T...> const &){}
template<int n, class...T>
typename enable_if<(n< sizeof...(T))>::type
_ot(ostream &os, tuple<T...> const &t){
    os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t);
}
template<class...T>
ostream & operator << (ostream &os, tuple<T...> const &t){
    _ot<0>(os, t); return os;
}
template<class T, class U>
ostream & operator<<(ostream &os, pair<T,U> const &p){
    return os << "(" << p.first << ", " << p.second << ") ";
}
template<class T>
ostream & operator<<(ostream &os, vector<T> const &v){
    rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os;
}
#ifdef DEBUG
#define dump(...) (cerr << #__VA_ARGS__ << " = " << mt(__VA_ARGS__) \
                   << " [" << __LINE__ << "]" << endl)
#else
#define dump(...)
#endif
void fastios(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#define endl '\n'
}
template<class T>
size_t uniq(vector<T> &v){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v.size();
}
template<class T>
size_t uniq(T *l, size_t n){
    sort(l,l+n);
    return unique(l,l+n) - l;
}
#define mems(arr,val) memset(arr,val,sizeof(arr));
int const mod = 1000000007;
int const inf = numeric_limits<int>::max()/8;

typedef int Capacity;
struct Edge {
    int src, dst;
    Capacity cap;
    Edge(int src_, int dst_, Capacity cap_) :
        src(src_), dst(dst_), cap(cap_) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

struct Dinic {
    int n, s, t;
    vector<int> level, iter;
    vector<vector<Capacity>> cap, flow;
    vector<vector<int>> g;
    Capacity inf;
    Dinic(int n)
        : n(n), cap(n, vector<Capacity>(n)), flow(n, vector<Capacity>(n)),
          g(n, vector<int>()), inf(numeric_limits<Capacity>::max()/8){}
    Dinic(const Graph &graph){
        *this = Dinic(graph.size());
        rep(i,n) for(auto &e : graph[i]) addEdge(e.src, e.dst, e.cap);
    }
    void addEdge(int u, int v, Capacity c){
        cap[u][v] += c; cap[v][u] += c; flow[v][u] += c;
        g[u].push_back(v); g[v].push_back(u);
    }
    Capacity residue(int u, int v){
        return cap[u][v] - flow[u][v];
    }
    Capacity solve(int s, int t){
        this->t = t, this->s = s;
        Capacity res = 0, aug = 1;
        while(aug > 0){
            levelize();
            iter.assign(n, 0);
            aug = augment(s, inf);
            res += aug;
        }
        return res;
    }
    void levelize(){
        level.assign(n, inf); level[s] = 0;
        queue<int> q; q.emplace(s);
        while(q.size()){
            int v = q.front(); q.pop();
            for(const int &d : g[v]){
                if(level[d] <= level[v] + 1 || residue(v,d) == 0) continue;
                level[d] = level[v] + 1; q.emplace(d);
            }
        }
    }
    Capacity augment(int v, Capacity lim){
        Capacity res = 0;
        if(v == t) return lim;
        for(int i = iter[v]; i < (int)g[v].size(); i++){
            const int &d = g[v][i];
            if(residue(v,d) == 0 || level[v] + 1 != level[d]) continue;
            Capacity aug = augment(d, min(lim, residue(v,d)));
            if(aug > 0){
                lim -= aug;
                flow[v][d] += aug; flow[d][v] -= aug;
                res += aug;
                if(lim == 0) return res;
            }
        }
        return res;
    }
};

int main(){
    fastios();
    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];
        Dinic d(n+m+2);
        int s = n+m, t = n+m+1;
        rep(i,m) d.addEdge(i+n,t,1);
        rep(i,n){
            d.addEdge(s,i,1);
            rep(j,m) if(__gcd(a[i],b[j]) != 1) d.addEdge(i,n+j,1);
        }
        rep(i,n)rep(j,m){
            if(d.flow[i][j+n]) dump(i,j, d.flow[i][j+m]);
        }
        cout << d.solve(s,t) << endl;
    }
}

// int main(){
//     int N,M;
//     cin >> N >> M;
//     Graph g(N);
//     rep(i,M){
//         int a,b,c;
//         cin >> a >> b >> c;
//         g[a].emplace_back(a,b,c);
//     }
//     Dinic dinic(g);
//     cout << dinic.solve(0,N-1) << endl;
// }

Measured memory_bytes: 10612