// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



// ford-fulkerson

struct edge {

    int to, cap, rev;

};



using edges = std::vector<edge>;

using graph = std::vector<edges>;



void add_edge(graph& g, int from, int to, int cap) {

    g[from].push_back(edge{to, cap, static_cast<int>(g[to].size())});

    g[to].push_back(edge{from, 0, static_cast<int>(g[from].size()-1)});

}



int dfs(graph& g, std::vector<bool>& used, int v, int t, int f) {

    if(v == t) {

        return f;

    }

    used[v] = true;

    for(int i=0; i<g[v].size(); ++i) {

        edge& e = g[v][i];

        if(!used[e.to] && e.cap > 0) {

            int d = dfs(g, used, e.to, t, std::min(f, e.cap));

            if(d > 0) {

                e.cap -= d;

                g[e.to][e.rev].cap += d;

                return d;

            }

        }

    }

    return 0;

}



int max_flow(graph& g, int s, int t) {

    int flow = 0;

    int INF = 1e9;

    std::vector<bool> used(g.size(), false);

    while(true) {

        std::fill(used.begin(), used.end(), false);

        int f = dfs(g, used, s, t, INF);

        if(f == 0) {

            return flow;

        }

        flow += f;

    }



}



int main() {

    int m, n;

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

        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];

        }

        graph g(n + m + 2);

        int const source = n + m;

        int const sink = source + 1;

        for(int i = 0; i < m; ++i) {

            add_edge(g, source, i, 1);

            for(int j = 0; j < n; ++j) {

                if(__gcd(b[i], r[j]) != 1) {

                    add_edge(g, i, j + m, 1);

                }

            }

        }

        for(int i = 0; i < n; ++i) {

            add_edge(g, i + m, sink, 1);

        }

        cout << max_flow(g, source, sink) << endl;

    }

}

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



#define REP(i,n) for(ll i=0;i<ll(n);++i)

#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)

#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)

#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)

#define ALL(v) (v).begin(),(v).end()

#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }

#define INF 1000000001ll

#define MOD 1000000007ll

#define EPS 1e-9



const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };

const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };





using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vl;

typedef vector<vi> vvi;

typedef vector<vl> vvl;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

ll max(ll a, int b) { return max(a, ll(b)); }

ll max(int a, ll b) { return max(ll(a), b); }

ll min(ll a, int b) { return min(a, ll(b)); }

ll min(int a, ll b) { return min(ll(a), b); }

///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///



struct Edge { int to, cap, rev, cost; };

typedef vector<Edge> Edges;

typedef vector<Edges> Graph;



struct MaxFlow {

	Graph G;

	vi level, iter;

	MaxFlow(Graph g) {

		int n = g.size();

		level.resize(n);

		iter.resize(n);

		G = g;

	}

	void add_edge(int from, int to, int cap, int cost = 0) {

		G[from].push_back(Edge{ to, cap, (int)G[to].size(),cost });

		G[to].push_back(Edge{ from,0,(int)G[from].size() - 1,-cost });

	}



	void bfs(int s) {

		fill(ALL(level), -1);

		queue<int> q;

		level[s] = 0;

		q.push(s);

		while (!q.empty()) {

			int v = q.front(); q.pop();

			for (int i = 0; i < G[v].size(); i++) {

				Edge &e = G[v][i];

				if (e.cap > 0 && level[e.to] < 0) {

					level[e.to] = level[v] + 1;

					q.push(e.to);

				}

			}

		}

	}

	int dfs(int v, int t, int f) {

		if (v == t)return f;

		for (int &i = iter[v]; i < G[v].size(); i++) {

			Edge &e = G[v][i];

			if (e.cap > 0 && level[v] < level[e.to]) {

				int d = dfs(e.to, t, min(f, e.cap));

				if (d > 0) {

					e.cap -= d;

					G[e.to][e.rev].cap += d;

					return d;

				}

			}

		}

		return 0;

	}

	int max_flow(int s, int t) {

		int flow = 0;

		for (;;) {

			bfs(s);

			if (level[t] < 0)return flow;

			fill(ALL(iter), 0);

			int f;

			while ((f = dfs(s, t, INF)) > 0) {

				flow += f;

			}

		}

	}

};



int gcd(int a, int b) {

	if (b == 0)return a;

	return gcd(b, a%b);

}





int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);

	int m, n;

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

		vi b(m), r(n);

		REP(i, m) {

			cin >> b[i];

		}

		REP(i, n) {

			cin >> r[i];

		}

		Graph g(n + m + 2);

		MaxFlow f(g);

		REP(i, m) {

			REP(j, n) {

				if (gcd(b[i], r[j]) != 1) {

					f.add_edge(i + 1, j + m + 1, 1);

				}

			}

		}

		REP(i, m) {

			f.add_edge(0, i + 1, 1);

		}

		REP(i, n) {

			f.add_edge(i + m + 1, m + n + 1, 1);

		}

		cout << f.max_flow(0, m + n + 1) << endl;

	}

}

// Fastest known solution for this problem: