#include <bits/stdc++.h>
using namespace std;
const long long inf = 1000000000000000000LL;
const double EPS = 1e-9;
const long long mod = 1000000007ll;
const int maxn = 300500;
int a[maxn];
map<int, bool> bp;
map<int, int> fdp;
int g[maxn];
int pr[4000500], prCnt;
bool notPrime[4000500];
int f(int s) {
  if (s == 1) return 0;
  if (fdp.find(s) != fdp.end()) return fdp[s];
  for (int i = 0;; i++)
    if (s % pr[i] == 0)
      return fdp[s] = (((bp.find(pr[i]) == bp.end()) ? 1 : -1) + f(s / pr[i]));
    else if (pr[i] * pr[i] > s)
      return fdp[s] = (((bp.find(s) == bp.end()) ? 1 : -1) + f(1));
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
int main() {
  for (long long i = 2; i * i < 1000010000LL; i++)
    if (!notPrime[i]) {
      pr[prCnt++] = i;
      for (long long j = i * i; j < 4000500; j += i) notPrime[j] = 1;
    }
  int n, m, t;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < (int)(n); ++i) scanf("%d", &a[i]);
  for (int i = 0; i < (int)(m); ++i) {
    scanf("%d", &t), bp[t] = 1;
  }
  int ret = 0;
  g[0] = a[0];
  for (int i = 0; i < (int)(n); ++i) g[i] = gcd(g[i], a[i]), g[i + 1] = g[i];
  for (int i = n - 1; i >= 0; i--) {
    if (f(g[i]) < 0)
      for (int j = 0; j < (int)(i + 1); ++j) a[j] = a[j] / g[i], g[j] /= g[i];
  }
  for (int i = 0; i < (int)(n); ++i) ret += f(a[i]);
  printf("%d\n", ret);
}
