#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

namespace Flow {
    struct Edge {
        int to, capacity, cost, reverse;
        Edge(int to, int capacity, int cost, int reverse) :
            to(to), capacity(capacity), cost(cost), reverse(reverse) {}
    };
    template <int MaxN> class PrimalDual {
        int n = MaxN;
        vector<Edge> g[MaxN];
    public:
        void clear(int n) {
            this->n = n;
            for (int i = 0; i < n; ++i)
                g[i].clear();
        }
        void push(int from, int to, int capacity = 1, int cost = 0) {
            g[from].emplace_back(to, capacity, cost, g[to].size());
            g[to].emplace_back(from, 0, -cost, g[from].size() - 1);
        }
        pair<int, int> flow(int s, int t, int f = 1 << 30) {
            int flow = f, cost = 0;
            static int prevv[MaxN], preve[MaxN], dist[MaxN], h[MaxN];
            fill(h, h + n, 0);
            while (flow > 0) {
                fill(dist, dist + n, 1 << 30);
                dist[s] = 0;
                using P = pair<int, int>;
                priority_queue<P, vector<P>, greater<P>> q;
                for (q.emplace(0, s); q.size(); ) {
                    auto p = q.top();
                    q.pop();
                    int v = p.second;
                    if (dist[v] < p.first) continue;
                    for (auto& e : g[v]) {
                        int d = dist[v] + e.cost + h[v] - h[e.to];
                        if (e.capacity > 0 && dist[e.to] > d) {
                            dist[e.to] = d;
                            prevv[e.to] = v;
                            preve[e.to] = &e - &g[v][0];
                            q.emplace(d, e.to);
                        }
                    }
                }
                if (dist[t] == 1 << 30) break;
                for (int v = 0; v < n; ++v)
                    h[v] += dist[v];
                int d = flow;
                for (int v = t; v != s; v = prevv[v])
                    d = min(d, g[prevv[v]][preve[v]].capacity);
                flow -= d;
                cost += d * h[t];
                for (int v = t; v != s; v = prevv[v]) {
                    auto& e = g[prevv[v]][preve[v]];
                    e.capacity -= d;
                    g[v][e.reverse].capacity += d;
                }
            }
            return { f - flow, cost };
        }
    };
}

int main() {
    Flow::PrimalDual<1002> pd;
    for (int m, n; cin >> m >> n, m && n; ) {
        vector<int> a(m), b(n);
        for (int& i : a)
            cin >> i;
        for (int& i : b)
            cin >> i;
        pd.clear(m + n + 2);
        for (int i = 0; i < m; ++i)
            pd.push(m + n, i);
        for (int i = 0; i < n; ++i)
            pd.push(i + m, m + n + 1);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (gcd(a[i], b[j]) > 1)
                    pd.push(i, j + m);
            }
        }
        cout << pd.flow(m + n, m + n + 1).first << endl;
    }
    return 0;
}

Measured memory_bytes: 11460