#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int n, m;
int a[N], b[N], pre[N];
unordered_map<int, int> prime, F;

int calc(int x)
{
    if (x == 1) return 0;
    else if (F.count(x)) return F[x];
    int res = 0, temp = x;

    for (int i = 2; i <= x / i; i ++)
    {
        if (temp % i == 0)
        {
            bool tag = prime[i];
            while (temp % i == 0)
                res += tag ? -1 : 1, temp /= i;
        }
    }
    if (temp > 1) res += prime[temp] ? -1 : 1;
    return F[x] = res;
}

signed main()
{
    read(n, m);
    for (int i = 1; i <= n; i ++)
        read(a[i]), pre[i] = __gcd(pre[i - 1], a[i]);
    for (int i = 1; i <= m; i ++)
        read(b[i]), prime[b[i]] = true;

    int ans = 0;
    for (int i = 1; i <= n; i ++) ans += calc(a[i]);
    
    for (int i = n, cur = 1; i >= 1; i --)
    {
        pre[i] /= cur;
        if (ans - i * calc(pre[i]) > ans)
        {
            ans -= i * calc(pre[i]);
            cur *= pre[i];
        }
    }
    cout << ans << '\n';

    return 0;
}