#include <bits/stdc++.h>
using namespace std;
const int mx = 5e3 + 10;
int d[mx];
int mcd[mx];
set<int> bad;
int gcd(int a, int b) {
  if (a % b == 0)
    return b;
  else
    return gcd(b, a % b);
}
int beauty(int v) {
  int b = 0, e;
  for (int p = 2; p * p <= v + 1; p++) {
    e = 0;
    while (v % p == 0) {
      e++;
      v /= p;
    }
    if (e > 0) {
      if (bad.count(p) == 1)
        b -= e;
      else
        b += e;
    }
  }
  if (v != 1) {
    if (bad.count(v) == 1)
      b--;
    else
      b++;
  }
  return b;
}
int main() {
  int n, m, v;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", d + i);
    if (i == 0)
      mcd[i] = d[i];
    else
      mcd[i] = gcd(mcd[i - 1], d[i]);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d", &v);
    bad.insert(v);
  }
  int div = 1;
  int ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    v = mcd[i] / div;
    if (beauty(v) < 0) {
      div = mcd[i];
    }
    ans += beauty(d[i] / div);
  }
  printf("%d\n", ans);
  return 0;
}
