#include <bits/stdc++.h>
using namespace std;
int n, m, cnt = 0, ans = 0, a[5005], b[5005], g[5005], bo[100005], prime[70005];
map<int, int> c;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void prime_init() {
  memset(bo, 0, sizeof(bo));
  for (int i = 2; i <= 100000; i++)
    if (!bo[i])
      for (int j = i * 2; j <= 100000; j += i) bo[j] = 1;
  for (int i = 2; i <= 100000; i++)
    if (!bo[i]) prime[++cnt] = i;
}
int f(int x) {
  if (x == 1) return 0;
  int s = 0;
  for (int i = 1; i <= cnt && x > 1; i++) {
    while (x % prime[i] == 0) {
      x /= prime[i];
      s += (c.count(prime[i]) ? -1 : 1);
    }
  }
  if (x > 1) s += (c.count(x) ? -1 : 1);
  return s;
}
int main() {
  scanf("%d%d", &n, &m);
  prime_init();
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (i == 1)
      g[i] = a[i];
    else
      g[i] = gcd(g[i - 1], a[i]);
  }
  for (int i = 1; i <= m; i++) {
    int x;
    scanf("%d", &x);
    c[x] = 1;
  }
  for (int i = 1; i <= n; i++) ans += f(a[i]);
  int last = 1;
  for (int i = n; i >= 1; i--) {
    if (g[i] / last <= 1) continue;
    int now = g[i] / last, d = f(now);
    if (d < 0) {
      last *= now;
      ans -= i * d;
    }
  }
  printf("%d\n", ans);
  return 0;
}
