#include <bits/stdc++.h>
using namespace std;
bool f[1000001];
long long p[1000001], G[5123];
long long A[5123], B[5123];
long long N, M, ct = 0;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void pre() {
  memset(f, false, sizeof(f));
  p[ct++] = 2;
  for (long long i = 3; i < 1000001; i += 2) {
    if (f[i]) continue;
    p[ct++] = i;
    for (long long j = i * i; j < 1000001; j += i) f[j] = true;
  }
}
long long func(long long v) {
  long long res = 0;
  long long mx = v;
  for (long long i = 0; i < ct && p[i] * p[i] <= mx; ++i) {
    long long cnt = 0;
    while (v % p[i] == 0) v /= p[i], ++cnt;
    if (cnt == 0) continue;
    long long add = (binary_search(B, B + M, p[i])) ? -1 : 1;
    res += cnt * add;
  }
  if (v != 1 && binary_search(B, B + M, v))
    --res;
  else if (v != 1)
    ++res;
  return res;
}
void solve() {
  cin >> N >> M;
  for (long long i = 0; i < N; ++i) cin >> A[i];
  for (long long i = 0; i < M; ++i) cin >> B[i];
  G[0] = A[0];
  for (long long i = 1; i < N; ++i) G[i] = gcd(G[i - 1], A[i]);
  long long ans = 0;
  for (long long i = 0; i < N; ++i) ans += func(A[i]);
  long long div = 1;
  for (long long i = N - 1; i >= 0; --i) {
    long long v = G[i] / div;
    long long res = func(v);
    if (res < 0) res = -res, ans += res * (i + 1), div = div * v;
  }
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  pre();
  solve();
  return 0;
}
