#include <bits/stdc++.h>
using namespace std;
long long n, m, cnt, a[50001], g[50001];
long long prime[2000000], pr[100000];
map<long long, long long> mp;
map<long long, long long> bpr;
long long gcd(long long x, long long y) {
  if (x < y) swap(x, y);
  return (x % y == 0) ? y : gcd(y, x % y);
}
long long f(long long x) {
  long long res = 0, r = 0;
  if (x == 1) return 0;
  if (bpr[x])
    return -1;
  else if (x <= 1000000 && prime[x])
    return 1;
  else {
    res = 0;
    for (long long i = 1; i <= 9000; i++)
      if (x % pr[i] == 0)
        if (bpr[pr[i]])
          while (x % pr[i] == 0) {
            x /= pr[i];
            res--;
          }
        else
          while (x % pr[i] == 0) {
            x /= pr[i];
            res++;
          }
  }
  if (x > 1) {
    if (bpr[x])
      res--;
    else
      res++;
  }
  return res;
}
signed main() {
  for (long long i = 2; i <= 1000000; i++) prime[i] = 1;
  prime[1] = 0;
  prime[2] = 1;
  for (long long i = 2; i <= 1000000; i++)
    if (prime[i])
      for (long long j = i * 2; j <= 1000000; j += i) prime[j] = 0;
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  long long x;
  for (long long i = 1; i <= m; i++) cin >> x, bpr[x] = 1;
  for (long long i = 2; i <= 100000; i++)
    if (prime[i]) pr[++cnt] = i;
  long long ans = 0;
  for (long long i = 1; i <= n; i++) ans += f(a[i]);
  g[1] = a[1];
  for (long long i = 2; i <= n; i++) g[i] = gcd(g[i - 1], a[i]);
  for (long long i = n; i >= 1; i--) {
    long long t = f(g[i]);
    if (t < 0)
      for (long long j = 1; j <= i; j++) g[j] /= g[i], ans -= t;
  }
  cout << ans;
  return 0;
}
