#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

//#define int long long
#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod


struct edge {
    int to, cap, rev;
    edge (int to, int cap, int rev) : to(to), cap(cap), rev(rev) {}
};


void add_edge(int from, int to, int cap, vector<vector<edge>>& G) {
    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, vector<bool>& used, vector<vector<edge>>& G) {
    if (v == t) return f;
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (!used[e.to] && e.cap > 0) {
            int d = dfs(e.to, t, min(f, e.cap), used, G);
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t, vector<bool>& used, vector<vector<edge>>& G) {
    int flow = 0;
    for(;;) {
        fill(used.begin(), used.end(), false);
        int f = dfs(s, t, INT_MAX, used, G);
        if (f == 0) return flow;
        flow += f;
    }
    return flow;
}

map<int, int> primefactor(int x) {
    map<int, int> fac;
    for (int i = 2; i * i <= x; i++){
        while (x % i == 0) {
            fac[i]++;
            x = x / i;
        }
    }
    if (x != 1) fac[x] += 1;
    return fac;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (true) {
        int n, m;
        cin >> n >> m;
        if (n == 0) break;
        int a[505] = {};
        int b[505] = {};
        vector<map<int, int>> mp1;
        vector<map<int, int>> mp2;
        rep(i, n) {
            cin >> a[i];
            map<int, int> tmp = primefactor(a[i]);
            mp1.push_back(tmp);
        }
        rep(i, m) {
            cin >> b[i];
            map<int, int> tmp = primefactor(b[i]);
            mp2.push_back(tmp);
        }
        vector<vector<edge>> G(1005);
        vector<bool> used(1005);
        int st = n + m, ed = n + m + 1;
        rep(i, n) add_edge(st, i, 1, G);
        rep(j, m) add_edge(n + j, ed, 1, G);

        bool check[505][505] = {};
        rep(i, n) {
            for (auto p : mp1[i]) {
                rep(j, m) {
                    if (!check[i][j] && mp2[j][p.fi] >= 1) {
                        check[i][j] = true;
                        add_edge(i, n + j, 1, G);
                        continue;
                    }
                }
            }
        }
        cout << max_flow(st, ed, used, G) << endl;
    }
}

Measured memory_bytes: 15384