#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 50010;
set<long long> bad;
long long gcd[MAXN], a[MAXN], n, m, prime[1000005], tot;
bool bo[10000005];
long long Gcd(long long x, long long y) {
  if (x < y) {
    long long k = x;
    x = y;
    y = k;
  }
  if (x % y == 0)
    return y;
  else
    return Gcd(y, x % y);
}
long long score(long long now) {
  long long ans = 0;
  for (long long i = 1; i <= tot && now > 1; ++i)
    if (now % prime[i] == 0) {
      while (now % prime[i] == 0 && now > 1) {
        now = now / prime[i];
        if (bad.find(prime[i]) == bad.end())
          ans++;
        else
          ans--;
      }
    }
  if (now == 1) return ans;
  if (bad.find(now) == bad.end())
    ans++;
  else
    ans--;
  return ans;
}
int main() {
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
    if (i == 1)
      gcd[1] = a[1];
    else
      gcd[i] = Gcd(a[i], gcd[i - 1]);
  }
  for (long long i = 1; i <= m; ++i) {
    long long x;
    scanf("%lld", &x);
    bad.insert(x);
  }
  bo[1] = 1;
  for (register long long i = 2; i <= sqrt(1e9) + 233; ++i) {
    if (!bo[i]) {
      ++tot;
      prime[tot] = i;
    }
    for (register long long j = 1; j <= tot && i * prime[j] <= sqrt(1e9) + 233;
         ++j) {
      bo[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
  long long lgcd = 1;
  for (long long i = n; i >= 1; --i) {
    if (score(gcd[i] / lgcd) < 0) {
      lgcd = gcd[i];
    }
    a[i] = a[i] / lgcd;
  }
  long long ans = 0;
  for (long long i = 1; i <= n; ++i) ans += score(a[i]);
  printf("%lld", ans);
  return 0;
}
