#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
namespace boost {template <class T>struct integer_iterator {T a;bool operator != (integer_iterator const & it) const { return a != it.a; }T operator * () const { return a; }integer_iterator & operator ++ () { ++ a; return *this; }integer_iterator operator ++ (int) { return { a ++ }; }};template <class T>struct integer_range {T l, r;typedef integer_iterator<T> iterator;iterator begin() const { return { l }; }iterator end  () const { return { r }; }};template <class T>integer_range<T> irange(T l, T r) { return { l, r }; }template <class T>struct integer_iterator_with_step {T a, d, i;bool operator != (integer_iterator_with_step const & it) const { return a != it.a or d != it.d or i != it.i; }T operator * () const { return a+d*i; }integer_iterator_with_step & operator ++ () { ++ i; return *this; }integer_iterator_with_step operator ++ (int) { return { a, d, i ++ }; }};template <class T>struct strided_integer_range {T l, r, s;typedef integer_iterator_with_step<T> iterator;iterator begin() const { return { l, s, 0 }; }iterator end  () const { return { l, s, (r - l) / s + 1 }; }};template <class T>strided_integer_range<T> irange(T l, T r, T s) { return { l, r, s }; }}
template <typename T>class ford_fulkerson {public:struct edge_t { int to; T cap; int rev; };static T infinity;ford_fulkerson(int n) : graph(n) {}std::vector<std::vector<edge_t> > graph; // adjacency list
void add_edge(int from, int to, T cap) {graph[from].push_back((edge_t){   to, cap, (int)graph[  to].size() });graph[  to].push_back((edge_t){ from,   0, (int)graph[from].size() - 1 });}std::vector<bool> used;T run_destructive(int s, int t) {T flow = 0;used.resize(graph.size());while (true) {std::fill(used.begin(), used.end(), false);T f = dfs(s, t, infinity);if (f == 0) return flow;flow += f;}}// search for augmenting pathes from `v' to `t', returns the volume of water `f'
T dfs(int v, int t, T f) {if (v == t) return f; // base case
used[v] = true;for (int i : boost::irange<int>(0,graph[v].size())) { // for each adjacent nodes which are not used and able to flow
edge_t & e = graph[v][i];const int w = e.to;if (not used[w] and 0 < e.cap) {T d = dfs(w, t, std::min(f, e.cap)); // v -> w ->> t
if (0 < d) { // let flow and make reverse capacity
e.cap -= d;graph[w][e.rev].cap += d;return d;}}}return 0; // path not found
}};template<> int ford_fulkerson<int>::infinity = 1<<28;template<> long long ford_fulkerson<long long>::infinity = 1ll<<58;template<> double ford_fulkerson<double>::infinity = 1/(double)0;
namespace boost {namespace math {template <typename T>T gcd(T a, T b) {if (b <= a) std::swap(a,b);while (a) {T a0 = a;a = b % a0;b = a0;}return b;}template <typename T>T lcm(T a, T b) {return (a * b) / gcd(a,b);}}}
#define repeat(i,n) for (int i = 0; (i) < (int)(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (int)(n); ++(i))
using namespace std;
int main() {
    while (true) {
        int m, n; cin >> m >> n;
        if (m == 0 and n == 0) break;
        vector<int> b(m), r(n);
        repeat (i,m) cin >> b[i];
        repeat (i,n) cin >> r[i];
        ford_fulkerson<int> g(m+n+2);
        repeat (i,m) g.add_edge(m+n,i,1);
        repeat (i,n) g.add_edge(m+i,m+n+1,1);
        repeat (i,m) repeat (j,n) {
            if (boost::math::gcd(b[i], r[j]) != 1) {
                g.add_edge(i,m+j,1);
            }
        }
        cout << g.run_destructive(m+n,m+n+1) << endl;
    }
    return 0;
}

Measured memory_bytes: 5644