#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:512000000")
using namespace std;
const double EPS = 1e-6;
const int INF = 1000 * 1000 * 1000;
const char CINF = 102;
const long long LINF = INF * 1ll * INF;
const long double PI = 3.1415926535897932384626433832795;
long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
const int nmax = 32000;
int pr[nmax + 1];
int lp[nmax + 1], ind;
void era() {
  int i, j;
  ind = 0;
  for (i = 2; i <= nmax; i++) {
    if (lp[i] == 0) {
      pr[ind++] = i;
      lp[i] = i;
    }
    for (j = 0; j < ind && i * pr[j] <= nmax && pr[j] <= lp[i]; j++)
      lp[i * pr[j]] = pr[j];
  }
}
int n, m, a[5100], b[5100], g[5100];
map<int, int> M;
int cb = 0, cg = 0;
int dv(int num) {
  int cb = 0, cg = 0;
  for (int i = 0; i < ind; i++) {
    while (num % pr[i] == 0) {
      num /= pr[i];
      if (1 == M[pr[i]])
        cb++;
      else
        cg++;
    }
  }
  if (num == 1) return cg - cb;
  if (M[num] == 1)
    cb++;
  else
    cg++;
  return cg - cb;
}
int main() {
  era();
  scanf("%d %d", &n, &m);
  for (int i = 0; i < (n); ++i) scanf("%d", &a[i]);
  for (int i = 0; i < (m); ++i) {
    scanf("%d", &b[i]);
    M[b[i]] = 1;
  }
  g[0] = a[0];
  for (int i = 0; i < (n - 1); ++i) {
    g[i + 1] = gcd(g[i], a[i + 1]);
  }
  int p = 1, zcur = 0, z = 0;
  for (int i = n - 1; i >= 0; i--) {
    int z = dv(g[i] / p);
    if (z <= 0) p = g[i];
    a[i] /= p;
  }
  int ans = 0;
  for (int i = 0; i < (n); ++i) {
    if (a[i] != 1) ans += dv(a[i]);
  }
  cout << ans << endl;
}
