#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <climits>
#include <fstream>
#include <random>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define revrep(i, n) for(int i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
#define chmin(x, y) x = min(x, y);
#define chmax(x, y) x = max(x, y);
#define sz(x) ((int)(x).size())

//const ll INFL = LLONG_MAX;//10^18 = 2^60
const ll INFL = 1LL<<60;
//const int INF = INT_MAX;
const int INF = 1 << 30;//10^9
ll MOD = 1000000007;
//const ll MOD = 998244353;
double EPS = 1e-10;

vector<ll> dy = {0, 1, 0, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, 0, -1, 0, 1, -1, 1, -1, 0};

void pres(double A){printf("%.12lf\n", A);}
void BinarySay(ll x, ll y = 60){rep(i, y) cout << (x>>(y-1-i) & 1); cout << endl;}
ll cnt_bit(ll x){return __builtin_popcountll(x);}

ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x; k /= 2;
  }
  return res;
}

ll pow_mod(ll x, ll k){
  x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

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

ll lcm(ll x, ll y){
  ll res = x / gcd(x, y);
  res *= y;
  return res;
};


#define MAX_V 2000
struct edge {ll to, cap, rev;};
vector<edge> G[MAX_V];
ll level[MAX_V];
ll iter[MAX_V];

void init_flow(){
  rep(i, MAX_V){
    G[i].resize(0);
  }
}

void add_edge(ll from, ll to, ll cap){
  G[from].push_back((edge){to, cap, (ll)G[to].size()});
  G[to].push_back((edge){from, 0, (ll)G[from].size() - 1});
}

void bfs(ll s){
  rep(i, MAX_V) level[i] = -1;
  queue<ll> que;
  level[s] = 0;
  que.push(s);
  while(!que.empty()){
    ll v = que.front(); que.pop();
    for(ll i = 0; i < G[v].size(); i++){
      edge &e = G[v][i];
      if(e.cap > 0 && level[e.to] < 0){
        level[e.to] = level[v] + 1;
        que.push(e.to);
      }
    }
  }
}

ll dfs(ll v, ll t, ll f){
  if(v == t) return f;
  for(ll &i = iter[v]; i < G[v].size(); i++){
    edge &e = G[v][i];
    if(e.cap > 0 && level[v] < level[e.to]){
      ll d = dfs(e.to, t, min(f, e.cap));
      if(d > 0){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

ll max_flow(ll s, ll t){
  ll flow = 0;
  for(;;){
    bfs(s);
    if(level[t] < 0) return flow;
    rep(i, MAX_V) iter[i] = 0;
    ll f;
    while((f = dfs(s, t, INFL)) > 0){
      flow += f;
    }
  }
}



int n, m;
int a[510], b[510];
void solve(){
  while(true){
    cin >> n >> m;
    if(n == 0 && m == 0) return;
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];
    init_flow();
    rep(i, n)rep(j, m){
      if(gcd(a[i], b[j]) != 1){
        add_edge(i, 600+j, 1);
      }
    }
    int s = 1200, t = 1201;
    rep(i, n){
      add_edge(s, i, 1);
    }
    rep(i, m){
      add_edge(600+i, t, 1);
    }
    cout << max_flow(s, t) << endl;
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  solve();
}



Measured memory_bytes: 15852