#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <queue>
#include <vector>
#include <map>
#include <assert.h>

using namespace std;
typedef long long ll;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define DEC(i, s) for (int i = (s); i >= 0; i--)

#define MEMSET(v, h) memset((v), h, sizeof(v))
#define FIND(m, w) ((m).find(w) != (m).end())

typedef int Weight;
struct Edge {
  int src;
  int dest;
  Weight weight;
  Edge(int src, int dest, Weight weight) : src(src), dest(dest), weight(weight) {;}
  bool operator<(const Edge &rhs) const {
    if (weight == rhs.weight) { return weight > rhs.weight; }
    if (src != rhs.src) { return src < rhs.src; }
    return dest < rhs.dest;
  }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

Weight augment(Graph &g, Matrix &capacity, const vector<int> &level, vector<bool> &finished, int from, int t, Weight cur) {
  if (from == t || cur == 0) { return cur; }
  if (finished[from]) { return 0; }
  for (Edges::iterator it = g[from].begin(); it != g[from].end(); it++) {
    int to = it->dest;
    if (level[to] <= level[from]) { continue; }
    Weight f = augment(g, capacity, level, finished, to, t, min(cur, capacity[from][to]));
    if (f > 0) {
      capacity[from][to] -= f;
      capacity[to][from] += f;
      return f;
    }
  }
  finished[from] = true;
  return 0;
}

Weight MaxFlow(Graph &g, int s, int t) {
  int n = g.size();
  Matrix capacity(n, Array(n));
  for (int from = 0; from < n; from++) {
    for (Edges::iterator it = g[from].begin(); it != g[from].end(); it++) {
      int to = it->dest;
      capacity[from][to] += it->weight;
    }
  }
  int ans = 0;
  while (true) {
    vector<int> level(n, -1);
    level[s] = 0;
    queue<int> que;
    que.push(s);
    for (int d = n; !que.empty() && level[que.front()] < d; ) {
      int from = que.front();
      que.pop();
      if (from == t) { d = level[from]; }
      for (Edges::iterator it = g[from].begin(); it != g[from].end(); it++) {
        int to = it->dest;
        if (capacity[from][to] > 0 && level[to] == -1) {
          que.push(to);
          level[to] = level[from] + 1;
        }
      }
    }
    vector<bool> finished(n);
    bool end = true;
    while (true) {
      Weight f = augment(g, capacity, level, finished, s, t, 1000000000);
      if (f == 0) { break; }
      ans += f;
      end = false;
    }
    if (end) { break; }
  }
  return ans;
}

int maxFlow(const Graph &g, int s, int t) {
  const int n = g.size();
  Matrix capacity(n, Array(n, 0));
  for (int i = 0; i < n; i++) {
    for (Edges::const_iterator it = g[i].begin(); it != g[i].end(); it++) {
      capacity[it->src][it->dest] = it->weight;
    }
  }
  int ret = 0;
  vector<int> parent(n);
  while (true) {
    fill(parent.begin(), parent.end(), -1);
    priority_queue<Edge> que;
    que.push(Edge(s, s, 0));
    while (!que.empty()) {
      Edge node = que.top();
      que.pop();
      if (parent[node.dest] != -1) { continue; }
      parent[node.dest] = node.src;
      if (node.dest == t) { break; }
      int from = node.dest;
      for (Edges::const_iterator it = g[from].begin(); it != g[from].end(); it++) {
        int to = it->dest;
        if (capacity[from][to] == 0 || parent[to] != -1) { continue; }
        que.push(Edge(from, to, 0));
      }
    }
    if (parent[t] == -1) { break; }
    Weight flow = 2000000000;
    int from = parent[t];
    int to = t;
    while (from != to) {
      flow = min(flow, capacity[from][to]);
      from = parent[from];
      to = parent[to];
    }
    from = parent[t];
    to = t;
    while (from != to) {
      capacity[from][to] -= flow;
      capacity[to][from] += flow;
      from = parent[from];
      to = parent[to];
    }
    ret += flow;
  }
  return ret;
}



int gcd(int a, int b) {
  if (b == 0) { return a; }
  return gcd(b, a % b);
}

int m, n;
int blue[501];
int red[501];

int BLUE(int x) { return x; }
int RED(int x) { return m + x; }
int SOURCE() { return m + n; }
int DEST() { return m + n + 1; }
int SIZE() { return m + n + 2; }

int main() {
  while (scanf("%d %d", &m, &n), m|n) {
    Graph g(SIZE());
    REP(b, m) {
      scanf("%d", &blue[b]);
      g[SOURCE()].push_back(Edge(SOURCE(), BLUE(b), 1));
      g[BLUE(b)].push_back(Edge(BLUE(b), SOURCE(), 0));
    }
    REP(r, n) {
      scanf("%d", &red[r]);
      g[RED(r)].push_back(Edge(RED(r), DEST(), 1));
      g[DEST()].push_back(Edge(DEST(), RED(r), 0));
    }
    REP(b, m) {
      REP(r, n) {
        if (gcd(blue[b], red[r]) != 1) {
          g[BLUE(b)].push_back(Edge(BLUE(b), RED(r), 1));
          g[RED(r)].push_back(Edge(RED(r), BLUE(b), 0));
        }
      }
    }
    assert(maxFlow(g, SOURCE(), DEST()) == MaxFlow(g, SOURCE(), DEST()));
    int ans = maxFlow(g, SOURCE(), DEST());
    printf("%d\n", ans);
  }
}

Measured memory_bytes: 10000