#include <bits/stdc++.h>

using namespace std;

#define int long long
#define uint unsigned int
#define dotimes(i, n) for (int i = 0, i##max__ = (n); i < i##max__; i++)
#define whole(x, f, ...) ([&](decltype((x)) c__) { return (f)(begin(c__), end(c__), ## __VA_ARGS__); })(x)

int rint() { int x; scanf("%lld", &x); return x; }
void wint(int x) { printf("%lld\n", x); }

template<typename T> int size(T const& c) { return static_cast<int>(c.size()); }
template<typename T> bool maxs(T& a, T const& b) { return a < b ? a = b, true : false; }
template<typename T> bool mins(T& a, T const& b) { return a > b ? a = b, true : false; }
inline int lg(int x) { return 63 - __builtin_clzll(static_cast<unsigned int>(x)); }

#ifdef EBUG
#define INT_WIDTH ""
#include "debug.h"
#else
#define inspect(...) do {} while (0)
#define debugf(...) do {} while (0)
#define debugv(...) do {} while (0)
#endif

int dinic(const int s, const int t, vector<vector<tuple<int, int&, int&>>>& capacities) {
  const int n = ::size(capacities);
  int r = 0;
  queue<int> q;
  vector<int> levels, progresses;
  for (;;) {
    // BFS
    levels.assign(n, -1);
    q.emplace(s);
    levels[s] = 0;
    while (!q.empty()) {
      const int u = q.front(), l = levels[u] + 1;
      q.pop();
      for (auto&& p : capacities[u]) {
        int v = get<0>(p);
        if (levels[v] < 0 && get<1>(p) > 0) {
          levels[v] = l;
          q.emplace(v);
        }
      }
    }
    if (levels[t] < 0)
      break;
    // DFS
    progresses.assign(n, 0);
    function<int(int, int)> rec;
    rec = [&](int u, int f) {
      if (u == s)
        return f;
      const int l = ::size(capacities[u]);
      int r = 0;
      for (int& progress = progresses[u]; progress < l; progress++) {
        auto&& p = capacities[u][progress];
        int v = get<0>(p);
        if (get<2>(p) > 0 && levels[v] < levels[u]) {
          int x = rec(v, min(get<2>(p), f));
          if (x > 0) {
            get<1>(p) += x;
            get<2>(p) -= x;
            f -= x;
            r += x;
            if (f == 0)
              break;
          }
        }
      }
      return r;
    };
    r += rec(t, 1LL << 61);
  }
  return r;
}

template<typename T>
int dinic(const int n, const int s, const int t, T const& edges) {
  vector<vector<tuple<int, int&, int&>>> capacities(n);
  vector<pair<int, int>> underlying_capacities;
  underlying_capacities.reserve(edges.size());
  // p = ((u, v), (capacity of u -> v, capacity of v -> u))
  for (pair<pair<int, int>, pair<int, int>> const& p : edges) {
    underlying_capacities.push_back(p.second);
    auto& uc = underlying_capacities.back();
    capacities[p.first.first].emplace_back(p.first.second, uc.first, uc.second);
    capacities[p.first.second].emplace_back(p.first.first, uc.second, uc.first);
  }
  return dinic(s, t, capacities);
}

signed main() {
  for (;;) {
    const int m = rint();
    const int n = rint();
    if (!m && !n)
      break;
    vector<pair<pair<int, int>, pair<int, int>>> edges;
    vector<int> blues, reds;
    dotimes(i, m) {
      blues.emplace_back(rint());
      edges.emplace_back(make_pair(0, i+2), make_pair(1, 0));
    }
    dotimes(i, n) {
      reds.emplace_back(rint());
      edges.emplace_back(make_pair(1, i+m+2), make_pair(0, 1));
    }
    dotimes(i, m)
      dotimes(j, n)
        if (__gcd(blues[i], reds[j]) > 1)
          edges.emplace_back(make_pair(i+2, j+m+2), make_pair(1, 0));
    wint(dinic(m+n+2, 0, 1, edges));
  }
  return 0;
}



Measured memory_bytes: 16892