#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000 + 5;

int gcd(int a, int b) {
    for (int t; b; t = a, a = b, b = t % a);
    return a;
}

int N, M;
int a[MAX_N], g[MAX_N], av[MAX_N], gv[MAX_N], f[MAX_N];
set<int> b;

int get_val(int y) {
    int val = 0;
    for (int x: b) {
        for (; y % x == 0; y /= x) {
            val --;
        }
    }
    for (; ~y & 1; y >>= 1) val ++;
    for (int x = 3; x * x <= y; x += 2) {
        for (; y % x == 0; y /= x) {
            val ++;
        }
    }
    if (y > 1) val ++;
    return val;
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i ++) {
        scanf("%d", &a[i]);
        g[i] = gcd(g[i - 1], a[i]);
    }
    for (int i = 1, x; i <= M; i ++) {
        scanf("%d", &x);
        b.insert(x);
    }
    int sum = 0, ans;
    for (int i = 1; i <= N; i ++) {
        av[i] = get_val(a[i]);
        gv[i] = get_val(g[i]);
        sum += av[i];
        // printf("i=%d, a=%d, av=%d, g=%d, gv=%d\n", i, a[i], av[i], g[i], gv[i]);
    }
    ans = sum;
    for (int i = 1; i <= N; i ++) {
        f[i] = 1e9;
        for (int j = i; j >= 0; j --) {
            f[i] = min(f[i], f[j] + gv[i] * (i - j));
        }
        ans = max(ans, sum - f[i]);
        // printf("f[%d]=%d\n", i, f[i]);
    }
    printf("%d\n", ans);
    return 0;
}