#include <bits/stdc++.h>
using namespace std;
inline int log(const char *format, ...) { return 0; }
const double EPS = 10e-8;
const int MAX = 5005;
;
const int INF = 1 << 30;
const int LIMIT = 33000;
unordered_map<int, bool> bad;
unordered_map<int, vector<int> > factors;
vector<int> primes;
bool sieve[LIMIT];
int A[MAX];
int G[MAX];
void init() {
  for (int i = 2; i < LIMIT; i++)
    if (!sieve[i])
      for (int j = i * i; j < LIMIT; j += i) sieve[j] = true;
  for (int i = 2; i < LIMIT; i++)
    if (!sieve[i]) primes.push_back(i);
}
void compute_factors(int num) {
  if (factors.count(num) == 1) return;
  int key = num;
  int sr = sqrt(num);
  for (int j = 0; primes[j] <= sr && num > 1; j++) {
    while (num % primes[j] == 0) {
      factors[key].push_back(primes[j]);
      num /= primes[j];
    }
  }
  if (num > 1) factors[key].push_back(num);
}
int f(int s) {
  if (s == 1) return 0;
  if (factors.count(s) == 0) compute_factors(s);
  vector<int> &F = factors[s];
  int ans = 0;
  for (int f : F) {
    bool good = true;
    if (bad.count(f) == 1) good = !bad[f];
    if (good) {
      ans += 1;
    } else {
      ans -= 1;
    }
  }
  return ans;
}
int gcd(int a, int b) {
  if (a < b) swap(a, b);
  while (b > 0) {
    int t = a;
    a = b;
    b = t % b;
  }
  return a;
}
int sub(int beauty, int div) {
  if (factors.count(div) == 0) compute_factors(div);
  for (int f : factors[div]) {
    bool good = true;
    if (bad.count(f) == 1) good = !bad[f];
    if (good)
      beauty--;
    else
      beauty++;
  }
  return beauty;
}
int main(int argc, char **argv) {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &A[i]);
  for (int i = 0; i < m; i++) {
    int b;
    scanf("%d", &b);
    bad[b] = true;
  }
  init();
  for (int i = 0; i < n; i++) compute_factors(A[i]);
  for (int i = n - 1; i >= 0; i--) {
    int g = A[0];
    for (int j = 0; j <= i; j++) g = gcd(g, A[j]);
    int a = f(A[i]);
    int b = sub(a, g);
    if (b > a) {
      for (int j = 0; j <= i; j++) A[j] /= g;
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) ans += f(A[i]);
  printf("%d", ans);
  return EXIT_SUCCESS;
}
