#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

// greatest common divisor and least common multiple
// gcd is calculated by Euclidean Algorithm
// lcm = m * n / gcd(m,n)
template <typename T = int>
T gcd(T a, T b) {
    if (a < b)
        return gcd(b, a);
    if (b == 0)
        return a;
    T r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

template <typename T = int>
T lcm(T m, T n) {
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

// ref: https://github.com/beet-aizu/library/blob/master/flow/dinic.cpp
template <typename T, bool directed>
struct Dinic {
    struct edge {
        int to;
        T cap;   // capacity of the edge
        int rev; // index for to->from edge
        edge() {}
        edge(int to_, T cap_, int rev_) : to(to_), cap(cap_), rev(rev_) {}
    };
    T inf = numeric_limits<T>::max();
    vector<vector<edge>> G;
    vector<int> level, iter;
    Dinic(int n) : G(n), level(n), iter(n) {}

    void addEdge(int from, int to, T cap) {
        G[from].emplace_back(to, cap, G[to].size());
        G[to].emplace_back(from, directed ? 0 : cap, G[from].size() - 1);
    }
    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> que;
        level[s] = 0;
        que.emplace(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (edge &e : G[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.emplace(e.to);
                }
            }
        }
    }
    T dfs(int v, int t, T 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.to]) {
                T d = dfs(e.to, t, min(f, e.cap));
                if (d == 0)
                    continue;
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
        return 0;
    }
    T maxFlow(int s, int t, T lim) {
        T fl = 0;
        while (true) {
            bfs(s);
            if (level[t] < 0 || lim == 0)
                break;
            fill(iter.begin(), iter.end(), 0);
            while (true) {
                T f = dfs(s, t, lim);
                if (f == 0)
                    break;
                fl += f;
                lim -= f;
            }
        }
        return fl;
    }
    // returns maximum flow from s to t
    T maxFlow(int s, int t) { return maxFlow(s, t, inf); }
};
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    while (true) {
        int m, n;
        cin >> m >> n;
        if (m == 0)
            return 0;
        vector<int> b(m), r(n);
        for (int i = 0; i < m; ++i) {
            cin >> b[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> r[i];
        }
        Dinic<int, true> dinic(m + n + 2);
        int s = m + n, t = m + n + 1;
        for (int i = 0; i < m; ++i) {
            dinic.addEdge(s, i, 1);
        }
        for (int i = 0; i < n; ++i) {
            dinic.addEdge(i + m, t, 1);
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (gcd(b[i], r[j]) != 1)
                    dinic.addEdge(i, m + j, 1);
            }
        }
        cout << dinic.maxFlow(s, t) << "\n";
    }
    return 0;
}


Measured memory_bytes: 7384