#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
const long long INF = 1e17L;
const int inf = 0x3f3f3f3f;
const int maxn = 32000;
int prime[maxn], notprime[maxn], tot = 0, n, m;
void get_prime() {
  for (int i = 2; i < maxn; i++) {
    if (!notprime[i]) prime[++tot] = i;
    for (int j = 1; j <= tot && i * prime[j] < maxn; j++) {
      notprime[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
set<int> st;
int a[5005], b[5005], gcd[5005];
int GCD(int a, int b) {
  if (b == 0)
    return a;
  else
    return GCD(b, a % b);
}
int solve(int s) {
  int ans = 0, good;
  for (int i = 1; i <= tot && prime[i] <= s; i++) {
    if (st.count(prime[i]))
      good = -1;
    else
      good = 1;
    while (s % prime[i] == 0) {
      s /= prime[i];
      ans += good;
    }
  }
  if (s > 1) {
    if (st.count(s))
      ans--;
    else
      ans++;
  }
  return ans;
}
int main() {
  get_prime();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d", &b[i]);
    st.insert(b[i]);
  }
  for (int i = 1; i <= n; i++) {
    gcd[i] = GCD(gcd[i - 1], a[i]);
  }
  for (int i = n; i >= 1; i--) {
    int t = solve(gcd[i]);
    if (t < 0) {
      t = gcd[i];
      for (int k = i; k >= 1; k--) {
        a[k] /= t;
        gcd[k] /= t;
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) ans += solve(a[i]);
  printf("%d\n", ans);
  return 0;
}
