#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>

using namespace std;

/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
*/

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

struct Edge {
    ll rev, from, to;
    ll cap, original_cap;
    Edge(ll r, ll f, ll t, ll c) : rev(r), from(f), to(t), cap(c), original_cap(c) {};
};

struct Graph {
    vector<vector<Edge>> g;
    Graph(ll n) { g = vector<vector<Edge>>(n); };
    vector<Edge>& operator[](ll i) { return g[i]; }
    size_t size() {return g.size(); }
    Edge& redge(Edge e) {
        return g[e.to][e.rev];
    }
    void add_edge(ll from, ll to, ll cap) {
        g[from].push_back(Edge(g[to].size(), from, to, cap));
        g[to].push_back(Edge(g[from].size() - 1, to, from, 0));
    }
};

struct FordFulkerson {
    vector<bool> used;
    Graph& G;
    FordFulkerson(Graph& g) : G(g) {};
    ll dfs(ll v, ll t, ll f) {
        if(v == t) return f;
        used[v] = true;
        for(auto& e : G[v]) {
            if(used[e.to] || e.cap <= 0) continue;
            ll d = dfs(e.to, t, min(f, e.cap));
            if(d <= 0) continue;
            e.cap -= d;
            G.redge(e).cap += d;
            return d;
        }
        return 0;
    }
    ll max_flow(ll s, ll t) {
        ll flow = 0;
        while(true) {
            used.assign(G.size(), false);
            ll f = dfs(s, t, INFL);
            if(f == 0) return flow;
            else flow += f;
        }
        return 0;
    }
};

void solve() {
    vll ans;
    while(true) {
        ll n, m;
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        vll b(n), r(m);
        Graph g(n + m + 2);
        for(ll i = 0; i < n; i++) {
            cin >> b[i];
            g.add_edge(0, i + 1, 1);
        }
        for(ll i = 0; i < m; i++) {
            cin >> r[i];
            g.add_edge(i + n + 1, n + m + 1, 1);
        }
        for(ll i = 0; i < n; i++) {
            for(ll j = 0; j < m; j++) {
                if(__gcd(b[i], r[j]) > 1) {
                    g.add_edge(i + 1, j + n + 1, 1);
                }
            }
        }
        FordFulkerson f(g);
        ans.push_back(f.max_flow(0, n + m + 1));
    }
    for(auto i : ans) cout << i << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 15864