#include <bits/stdc++.h> // {{{

#define GET_MACRO(a, b, c, d, NAME, ...) NAME
#define REP(...) GET_MACRO(__VA_ARGS__, REP4, REP3, REP2)(__VA_ARGS__)
#define REP2(i, a) REP3(i, 0, a)
#define REP3(i, a, b) REP4(i, a, b, 1)
#define REP4(i, a, b, s) for (int i = (a); i < (int)(b); i += (s))
#define REPR(...) GET_MACRO(__VA_ARGS__, REPR4, REPR3, REPR2)(__VA_ARGS__)
#define REPR2(i, a) REPR3(i, 0, a)
#define REPR3(i, a, b) REPR4(i, a, b, 1)
#define REPR4(i, a, b, s) for (int i = (b)-1; i >= (int)(a); i -= (s))
#define ALL(c) (c).begin(), (c).end()
#define DUMP(x) (std::cerr << #x << ':' << ' ' << x << '\n')
#define TMPL_T template <typename T>
#define TMPL_TU template <typename T, typename U>
#define mut auto
#define let const auto

using Int = long long;
// clang-format off
namespace extio {
std::string delimiter=" ",pdelimiter=" ";
std::string bracket_b="",bracket_e="";
void chdelim(const std::string&s){delimiter=s;}
void chpdelim(const std::string&s){pdelimiter=s;}
void chbracket(const std::string&b,const std::string&e){bracket_b=b,bracket_e=e;}
TMPL_T  void pcont(std::ostream&os,const T&x){int c=0;for(const auto&a:x){if(c++)os<<delimiter;os<<a;}}
TMPL_TU void ppair(std::ostream&os,const std::pair<T,U>&p){os<<bracket_b<<p.first<<pdelimiter<<p.second<<bracket_e;}
}
namespace std {
TMPL_T ostream& operator<<(ostream&os,const vector<T>&x){extio::pcont(os,x);return os;}
TMPL_T ostream& operator<<(ostream&os,const set<T>&x){extio::pcont(os,x);return os;}
TMPL_T ostream& operator<<(ostream&os,const multiset<T>&x){extio::pcont(os,x);return os;}
TMPL_T ostream& operator<<(ostream&os,const deque<T>&x){extio::pcont(os,x);return os;}
TMPL_TU ostream& operator<<(ostream&os,const map<T,U>&x){extio::pcont(os,x);return os;}
TMPL_TU ostream& operator<<(ostream&os,const pair<T,U>&x){extio::ppair(os,x);return os;}
}
TMPL_TU inline bool chmax(T&x,U a){return x<a&&(x=a,1);}
TMPL_TU inline bool chmin(T&x,U a){return a<x&&(x=a,1);}

inline int in(){int x;std::cin>>x;return x;}

struct Initializer_ {
  Initializer_(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);
    std::cout << std::setprecision(10);
    std::cerr << std::setprecision(10);
  }
} precalc;
// clang-format on
// }}}

// {{{ orliv::graph::max_flow::FordFulkerson
// verify AOJ GRL_6_A
#include <algorithm>
#include <cstdlib>
#include <vector>
namespace orliv {
namespace graph {
namespace max_flow {
namespace fordfulkerson {
namespace internal {
struct BoolArray {
  int X;
  std::vector<int> flags;
  BoolArray(std::size_t N) : flags(N), X(0) {}
  void clear() { ++X; }
  bool get(int x) const { return flags[x] == X; }
  void set(int x) { flags[x] = X; }
};
}
}
struct FordFulkerson {
  struct Edge {
    int to;
    int cap;
    int rev;
    Edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev) {}
  };
  std::vector<std::vector<Edge>> G;
  fordfulkerson::internal::BoolArray used;
  FordFulkerson(int V) : G(V), used(V) {}
  void addEdge(int from, int to, int cap) {
    G[from].emplace_back(to, cap, G[to].size());
    G[to].emplace_back(from, 0, G[from].size() - 1);
  }
  int dfs(int v, int t, int f) {
    if (v == t) return f;
    used.set(v);
    for (auto &e : G[v]) {
      if (used.get(e.to)) continue;
      if (e.cap <= 0) continue;
      int d = dfs(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 getFlow(int s, int t) {
    int flow = 0;
    while (1) {
      used.clear();
      int f = dfs(s, t, 1 << 29);
      if (f == 0) return flow;
      flow += f;
    }
  }
};
}
}
}
// }}}

using namespace std;

signed main() {
  int M, N;
  while (M = in(), N = in(), M || N) {
    vector<int> A, B;
    A.reserve(M);
    B.reserve(N);
    REP(i, M) { A.emplace_back(in()); }
    REP(i, N) { B.emplace_back(in()); }
    orliv::graph::max_flow::FordFulkerson g(M + N + 2);
    REP(i, M) { g.addEdge(0, i + 1, 1); }
    REP(i, N) { g.addEdge(M + i + 1, M + N + 1, 1); }
    REP(i, M) REP(j, N) {
      if (__gcd(A[i], B[j]) != 1) { g.addEdge(i + 1, M + j + 1, 1); }
    }
    cout << g.getFlow(0, M + N + 1) << endl;
  }
  return 0;
}

Measured memory_bytes: 7528