// Original C++ solution (slower):
#include <algorithm>

#include <forward_list>

#include <functional>

#include <iostream>

#include <vector>

using namespace std;



#define rep(i, n) for (int i = 0; i < (int)(n); ++i)



int gcd(int n, int m) { return n ? gcd(m % n, n) : m; }



struct edge {

    int src;

    int dst;

    int cap;

    int flow;

};



typedef vector<vector<reference_wrapper<edge>>> graph;



void add_edge(graph& g, forward_list<edge>& edges, edge e)

{

    edges.push_front(e);

    g[e.src].push_back(edges.front());

    g[e.dst].push_back(edges.front());

}



inline int opposite(const edge& e, int v) { return (e.dst == v) ? e.src : e.dst; }

inline int residue(const edge& e, int dst) { return (e.dst == dst) ? e.cap - e.flow : e.flow; }

inline void augment(edge& e, int dst, int delta) { e.flow += (e.dst == dst) ? delta : -delta; }



int max_flow(graph& g, int src, int sink)

{

    edge dummy = { 0, 0, 0, 0 };

    int f = 0;

    for (;;) {

        vector<edge*> prev(g.size(), nullptr);

        vector<int> stack;

        stack.push_back(src);

        prev[src] = &dummy;

        while (!stack.empty()) {

            int v = stack.back(); stack.pop_back();

            if (v == sink)

                break;

            for (edge& e : g[v]) {

                int w = opposite(e, v);

                if (residue(e, w) > 0 && prev[w] == nullptr) {

                    prev[w] = &e;

                    stack.push_back(w);

                }

            }

        }

        if (prev[sink] == nullptr)

            return f;

        int delta = 1e9;

        for (int v = sink; prev[v] != &dummy; v = opposite(*prev[v], v))

            delta = min(delta, residue(*prev[v], v));

        for (int v = sink; prev[v] != &dummy; v = opposite(*prev[v], v))

            augment(*prev[v], v, delta);

        f += delta;

    }

}



int main()

{

    ios::sync_with_stdio(false);



    int m, n;

    while (cin >> m >> n, m) {

        vector<int> bs(m), rs(n);

        rep(i, m) cin >> bs[i];

        rep(i, n) cin >> rs[i];



        forward_list<edge> edges;

        graph g(n + m + 2);

        rep(i, m) rep(j, n) {

            if (gcd(bs[i], rs[j]) > 1) {

                add_edge(g, edges, { i, m + j, 1, 0 });

            }

        }

        rep(i, m) add_edge(g, edges, { m + n, i, 1, 0 });

        rep(j, n) add_edge(g, edges, { m + j, m + n + 1, 1, 0 });



        int f = max_flow(g, m + n, m + n + 1);

        cout << f << endl;

    }

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)

#define REP(i, n) FOR(i, 0, n)



struct Edge {

    int src, dst;

    Edge(int src, int dst): src(src), dst(dst) {}

};

using Vertex = vector<Edge>;

using Graph = vector<Vertex>;



void add_edge(Graph& graph, int src, int dst) {

    graph[src].emplace_back(src, dst);

    graph[dst].emplace_back(dst, src);

}



bool augment(const Graph& graph, vector<bool>& visited, vector<int>& match, int u) {

    if (u == -1) return true;

    for (auto& e : graph[u]) {

        if (!visited[e.dst]) {

            visited[e.dst] = true;

            if (augment(graph, visited, match, match[e.dst])) {

                match[e.src] = e.dst;

                match[e.dst] = e.src;

                return true;

            }

        }

    }

    return false;

}



int bipartie_matching(const Graph& graph, int n_left) {

    vector<int> match(graph.size(), -1);

    int n_match = 0;

    REP(u, n_left) {

        vector<bool> visited(graph.size());

        if (augment(graph, visited, match, u)) ++n_match;

    }

    return n_match;

}



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



int main() {

    cin.tie(0); ios_base::sync_with_stdio(false);



    int m, n;

    while (cin>>m>>n, m|n) {

        vector<int> blue(m), red(n);

        REP(i, m) cin >> blue[i];

        REP(i, n) cin >> red[i];



        Graph graph(m+n);

        REP(i, m) REP(j, n) {

            if (gcd(blue[i], red[j]) > 1)

                add_edge(graph, i, m+j);

        }



        cout << bipartie_matching(graph, m) << '\n';

    }

}

// Fastest known solution for this problem: