#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, que;
    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);
    }
    inline 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);
            res += (aug = augment(s, inf));
        }
        return res;
    }
    void levelize(){
        level.assign(n, inf); level[s] = 0;
        int l = 0, r = 0;
        que.assign(n+1, 0);
        que[r++] = s;
        while(l != r){
            int v = que[l++];
            for(const int &d : g[v]){
                if(level[d] <= level[v] + 1 || residue(v,d) == 0) continue;
                level[d] = level[v] + 1; que[r++] = 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;
            const Capacity aug = augment(d, min(lim, residue(v,d)));
            if(aug > 0){
                flow[v][d] += aug; flow[d][v] -= aug;
                res += aug; lim -= aug;
                if(lim == 0) return res;
            }
        }
        return res;
    }
};

int dp[2000][2000];
int gcd(int a, int b){
    return a < 2000 && b < 2000 ? dp[a][b] : __gcd(a,b);
}


int main(){
    rep(i,2000)rep(j,i+1) if(i*j) dp[i][j] = dp[j][i] = __gcd(i,j);
    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: 26236