const int N = 5001;
ll n, m, k;
ll arr[N];
unordered_set<ll> bb;
vector<ll> primes;
bool aprimes[33334];
int main() {
    // freopen("input.txt", "r", stdin); freopen("output.txt","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    REP(i,n) { cin >> arr[i]; }
    REP(i,m) { cin >> k; bb.insert(k); }
    ll maxp = 33334;
    REP(i,maxp) aprimes[i]=true;
    for (int i = 2; i < maxp; i++) {
        if (aprimes[i]) {
            primes.PB(i);
            for (int j = i * i; j < maxp; j+=i) {
                aprimes[j]=false;
            }
        }
    }
    dbgm(5);
    ll bestdiff = 0;
    ll tot = 0;
    ll d = arr[0];
    // dbg(primes);
    REP(i,n) {
        d = __gcd(d, arr[i]);
        ll currd = d;
        ll currdiff = 0;
        ll curr = arr[i];
        for (auto p : primes) {
            bool isbad = bb.count(p);
            while (curr%p==0) {
                curr/=p;
                if (isbad) tot--;
                else tot++;
            }
            while(currd%p==0) {
                currd/=p;
                if (isbad)currdiff++;
                else currdiff--;
            }
        }
        if (curr != 1) {
            if (bb.count(curr)) tot--;
            else tot++;
        }
        if (currd != 1) {
            if (bb.count(currd)) currdiff++;
            else currdiff--;
        }
        dbgm(i, d, currdiff);
        bestdiff=max(bestdiff, currdiff * (i+1));
    }
    dbgm(tot, bestdiff);
    cout << tot + bestdiff;

    return 0;
}