#include <bits/stdc++.h>
using namespace std;
const int maxn = 5050;
inline int getint() {
  int ans(0);
  char w = getchar();
  while (w < '0' || '9' < w) w = getchar();
  while ('0' <= w && w <= '9') {
    ans = ans * 10 + w - '0';
    w = getchar();
  }
  return ans;
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int n, m;
int num[maxn], gf[maxn];
set<int> Bad;
int prime[105000], nsk, sgn[105000];
inline void get_prime(int n) {
  memset(sgn, 0, sizeof sgn);
  for (int i = 2; i <= n; ++i) {
    if (!sgn[i]) prime[++nsk] = i;
    for (int j = 1; j <= nsk && prime[j] * i <= n; ++j) {
      sgn[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
inline int get_score(int k) {
  int ulim = ceil(sqrt(k));
  int ans = 0;
  for (int i = 1; prime[i] <= ulim; ++i)
    while (!(k % prime[i])) {
      if (Bad.count(prime[i]))
        ans--;
      else
        ans++;
      k /= prime[i];
    }
  if (k > 1)
    if (Bad.count(k))
      ans--;
    else
      ans++;
  return ans;
}
int main() {
  n = getint();
  m = getint();
  for (int i = 1; i <= n; ++i) {
    num[i] = getint();
    gf[i] = gcd(gf[i - 1], num[i]);
  }
  Bad.clear();
  for (int i = 1; i <= m; ++i) {
    int x = getint();
    Bad.insert(x);
  }
  get_prime(100000);
  int dived = 1, ans = 0, k;
  for (int i = n; i; --i) {
    if ((k = get_score(gf[i] / dived)) < 0) dived *= gf[i] / dived;
    ans += get_score(num[i]) - get_score(dived);
  }
  printf("%d\n", ans);
  return 0;
}
