#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define INF 1000000001
#define LL long long int

using namespace std;

int n, k;
vector < vector<int> > g;
vector<int> mt;
vector<bool> used;

bool try_kuhn (int v) {
	if (used[v])  return false;
	used[v] = true;
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (mt[to] == -1 || try_kuhn (mt[to])) {
			mt[to] = v;
			return true;
		}
	}
	return false;
}


int main () {

    int n;
    cin >> n;
    k = n;
    int a[n+1],b[n+1];
    g.resize(n+1); mt.resize(n+1);

    mt.assign (n+1, -1);

    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(__gcd(a[i],b[j])!=1)
                 g[i].pb(j);

// BIPARTITE MATCHING USING KUHNS ALGORITHM

    vector<char> used1 (n);
	for (int i=1; i<=n; ++i)
		for (size_t j=0; j<g[i].size(); ++j)
			if (mt[g[i][j]] == -1) {
				mt[g[i][j]] = i;
				used1[i] = true;
				break;
			}

    for (int v=1; v<=n; ++v) {
		if (used1[v])  continue;
		used.assign (n, false);
		try_kuhn (v);
	}

    int ans = 0;

	for (int i=1; i<=n; ++i)
		if (mt[i] != -1){
		//	printf ("%d %d\n", mt[i], i);
            ans++;
		}


    cout << ans;

    return 0;
}