#include <bits/stdc++.h>
using namespace std;
class DREAD {
  friend int fread();
  static const int buff_max = 20000000 + 10;
  char buf[buff_max], *pt;

 public:
  void clear() {
    for (; isspace(*pt); ++pt)
      ;
  }
  void Init() {
    buf[fread(buf, 1, buff_max, stdin)] = EOF;
    pt = buf;
  }
  bool eoln() { return *pt == '\n'; }
  inline bool eof() { return *pt == EOF; }
  int Int() {
    bool pos = 1;
    int res = 0;
    for (; !isdigit(*pt) && *pt != '-' && !eof(); ++pt)
      ;
    if (*pt == '-') pos = 0, ++pt;
    for (; isdigit(*pt); ++pt) res = res * 10 + (*pt - '0');
    return pos ? res : -res;
  }
} READ;
const int N_MAX = 5000 + 10;
int N, M, seq[N_MAX], bad[N_MAX];
namespace Nwork {
int gcd[N_MAX];
int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }
int p[N_MAX], e[N_MAX], cnt;
int exist(int p) { return *lower_bound(bad + 1, bad + M + 1, p) == p ? -1 : 1; }
int calc(int x) {
  cnt = 0;
  for (int i = 2, k = int(sqrt(x)); i <= k; ++i) {
    if (x == 1) break;
    if (x % i == 0) {
      p[++cnt] = i;
      for (e[cnt] = 0; x % i == 0; x /= i) ++e[cnt];
    }
  }
  if (x != 1) p[++cnt] = x, e[cnt] = 1;
  int ret = 0;
  for (int i = 1; i <= cnt; ++i) ret += exist(p[i]) * e[i];
  return ret;
}
void main() {
  gcd[1] = seq[1];
  for (int i = 2; i <= N; ++i) gcd[i] = GCD(gcd[i - 1], seq[i]);
  sort(bad + 1, bad + M + 1);
  for (int r = N; r >= 1; --r)
    if (calc(gcd[r]) < 0)
      for (int i = 1; i <= r; ++i) {
        seq[i] /= gcd[r];
        gcd[i] /= gcd[r];
      }
  int ret = 0;
  for (int i = 1; i <= N; ++i) ret += calc(seq[i]);
  printf("%d\n", ret);
}
}  // namespace Nwork
namespace Ninit {
void init() {
  N = READ.Int(), M = READ.Int();
  for (int i = 1; i <= N; ++i) seq[i] = READ.Int();
  for (int i = 1; i <= M; ++i) bad[i] = READ.Int();
}
}  // namespace Ninit
int main() {
  READ.Init();
  Ninit::init();
  Nwork::main();
  return 0;
}
