#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int p[(1 << 16) - 10], pri[(1 << 16) - 10], ps[(1 << 16) - 10],
    g[(1 << 16) - 10], gc[(1 << 16) - 10];
int n, m;
int cnt = 0;
int cred(int pp) {
  if (pp == 1) return 0;
  int ind = lower_bound(p, p + m, pp) - p;
  if (ind < m && p[ind] == pp) return -1;
  return 1;
}
int saldo(int a) {
  int sl = 0;
  for (int i = 0; ps[i] * ps[i] <= a && ps[i] * ps[i] > 0; i++) {
    if (a % ps[i] == 0) {
      int f = cred(ps[i]);
      while (a % ps[i] == 0) {
        a /= ps[i];
        sl += f;
      }
    }
  }
  sl += cred(a);
  return sl;
}
int main() {
  for (int i = 2; i <= (1 << 16) - 10; i++) {
    if (pri[i] == 0) {
      pri[i] = i;
      for (int j = i * i; j <= (1 << 16) - 10 && j > 0; j += i) {
        pri[j] = i;
      }
      ps[cnt++] = i;
    }
  }
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", g + i);
  for (int i = 0; i < m; i++) scanf("%d", p + i);
  gc[0] = g[0];
  int total = saldo(g[0]);
  for (int i = 1; i < n; i++) {
    gc[i] = gcd(gc[i - 1], g[i]);
    total += saldo(g[i]);
  }
  int foi = 1;
  for (int i = n - 1; i >= 0; i--) {
    gc[i] /= foi;
    if (gc[i] > 1) {
      int s = saldo(gc[i]);
      if (s < 0) {
        foi *= gc[i];
        total -= (i + 1) * s;
      }
    }
  }
  printf("%d\n", total);
  return 0;
}
