#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

struct Edge{
    int to, cap, rev;
    Edge() = default;
    Edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev) {}
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for(;;){
        int m, n;
        cin >> m >> n;
        if(m == 0 && n == 0)    return 0;
        vector<int> b(m), r(n);
        int V = m + n + 2;
        int s = m + n, t = s + 1;
        for(int i = 0; i < m; ++i)  cin >> b[i];
        for(int i = 0; i < n; ++i)  cin >> r[i];
        vector<vector<Edge>> graph(V);
        auto add_edge = [&](int u, int v, int cap){
            graph[u].emplace_back(v, cap, graph[v].size());
            graph[v].emplace_back(u, 0, (int)graph[u].size() - 1);
            return;
        };
        for(int i = 0; i < m; ++i)  add_edge(s, i, 1);
        for(int i = m; i < m + n; ++i)  add_edge(i, t, 1);
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(__gcd(b[i], r[j]) > 1)   add_edge(i, m + j, 1);
            }
        }

        vector<int> depth(V), iter(V);
        auto bfs = [&](int root) {
            for(int i = 0; i < V; ++i)  depth[i] = -1;
            depth[root] = 0;
            queue<int> que;
            que.emplace(root);
            while(!que.empty()){
                int from = que.front();
                que.pop();
                for(auto& e : graph[from]){
                    if(e.cap > 0 && depth[e.to] == -1){
                        depth[e.to] = depth[from] + 1;
                        que.emplace(e.to);
                    }
                }
            }
            return;
        };
        auto dfs = [&](auto&& self, int S, int T, int flow) -> int {
            if(S == T)  return flow;
            for(int& i = iter[S]; i < (int)graph[S].size(); ++i){
                auto& e = graph[S][i];
                if(e.cap > 0 && depth[S] < depth[e.to]){
                    int f = self(self, e.to, T, min(e.cap, flow));
                    if(f > 0){
                        e.cap -= f;
                        graph[e.to][e.rev].cap += f;
                        return f;
                    }
                }
            }
            return 0;
        };
        auto max_flow = [&](int S, int T) {
            int res = 0;
            for(;;){
                bfs(S);
                if(depth[T] < 0)    break;
                for(int i = 0; i < V; ++i)  iter[i] = 0;
                int f;
                while((f = dfs(dfs, S, T, INF)) > 0)    res += f;
            }
            return res;
        };

        cout << max_flow(s, t) << '\n';
    }
}


Measured memory_bytes: 7328