//52行目から編集
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > vvi;
typedef vector<vector<ll> > vvl;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

template<class T> bool chmin(T& a,T b){if(a > b){a = b;return true;}else return false;}
template<class T> bool chmax(T& a,T b){if(a < b){a = b;return true;}else return false;}
///////////////////////////////////////////////////////////
class BM {
private:
    struct edge {
        int to,cap,rev;
    };
    int U,V;
    vector<vector<edge> > G;
    vector<int> level;
    vector<int> iter;
 
public:
    BM(int u,int v) : U(u), V(v), G(U+V+2){
        for(int i = 0; i < U; i++){
            init_edge(0,i+1);
        }
        for(int i = 0; i < V; i++){
            init_edge(U+i+1,U+V+1);
        }
    }
    void init_edge(int from,int to) {
        G[from].push_back((edge){to,1,(int)G[to].size()});
    	G[to].push_back((edge){from,0,(int)G[from].size()-1});
    }
    void add_edge(int from,int to) {
        from += 1,to += U+1;
    	G[from].push_back((edge){to,1,(int)G[to].size()});
    	G[to].push_back((edge){from,0,(int)G[from].size()-1});
    }
    void bfs(int s) {
        fill(level.begin(),level.end(),-1);
    	queue<int> que;
    	level[s] = 0;
    	que.push(s);
    	while(!que.empty()){
            int v = que.front();
            que.pop();
            for(auto& e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    int dfs(int v,int t,int f) {
        if(v==t){
            return f;
        }
        for(int &i = iter[v];i<(int)G[v].size();i++){
            edge &e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                int 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;
    }
    int solve() {
        level.resize(U+V+2), iter.resize(U+V+2);
        int flow = 0;
        int s=0,t=U+V+1;
        for(;;){
            bfs(s);
            if(level[t] < 0) return flow;
            fill(iter.begin(),iter.end(),0);
            int f;
            while((f=dfs(s,t,numeric_limits<int>::max())) > 0){
                flow += f;
            }
        }
    }
    vector<int> allocate() {
        vector<int> res(U, -1);
        for(int i = 0; i < U; i++){
            for(auto& e : G[i+1]){
                if(e.cap == 0 && e.to != 0){
                    res[i] = e.to-U-1;
                    break;
                }
            }
        }
        return res;
    }
};

long long gcd(long long a, long long b) {
  return b != 0 ? gcd(b, a % b) : a;
}
long long lcm(long long a, long long b) {
  return a * b / gcd(a, b);
}
// a x + b y = gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(20);
    while(true){
        int m,n;cin >> m >> n;
        if(!m and !n)break;
        vector<int> a(m),b(n);
        rep(i,m)cin >> a[i];
        rep(i,n)cin >> b[i];
        BM G(m,n);
        rep(i,m){
            rep(j,n){
                if(gcd(a[i],b[j]) != 1){
                    G.add_edge(i,j);
                }
            }
        }
        cout << G.solve() << '\n';
    }
    return 0;
}



Measured memory_bytes: 7380