#pragma c99 on

#include <stdio.h>

#define MIN(A, B) ((A) < (B))? (A) : (B)

int NextInt() { int d; scanf("%d", &d); return d; }

typedef struct {
  int length;
  int dest[501];
} Edge;

int b[501], r[501];
Edge e[501];
int t[501];
int m, n;

int augment(int u, int used[]) {
  if (u < 0) {
    return 1;
  }
  for (int i = 0; i < e[u].length; i++) {
    int d = e[u].dest[i];
    if (!used[d]) {
      used[d] = 1;
      if (augment(t[d], used)) {
        t[d] = u;
        return 1;
      }
    }
  }
  return 0;
}

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

int main() {
  int i, j;
  int ans;
  while (1) {
    m = NextInt(); n = NextInt();
    if (m + n == 0) {
      break;
    }
    for (i = 0; i < m; i++) {
      e[i].length = 0;
      b[i] = NextInt();
    }
    for (i = 0; i < n; i++) {
      r[i] = NextInt();
      t[i] = -1;
    }
  
    for (i = 0; i < m; i++) {
      for (j = 0; j < n; j++) {
        if (gcd(b[i], r[j]) != 1) {
            e[i].dest[e[i].length++] = j;
        }
      }
    }
    ans = 0;
    for (i = 0; i < m; i++) {
      int used[1001] = { 0 };
      if (augment(i, used)) {
        ans++;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}