#include <bits/stdc++.h>
using namespace std;
int num, badpn, val[5005], badp[5005], t1, t2;
int pri[100005], prin, vis[100005];
void pre() {
  for (int i = 2; i < 100005; i++) {
    if (!vis[i]) {
      pri[prin++] = i;
    }
    vis[i] = 1;
    for (int j = 0; j < prin; j++) {
      if (i * pri[j] > 100004) {
        break;
      }
      vis[i * pri[j]] = 1;
      if (!(i % pri[j])) {
        break;
      }
    }
  }
}
int get_score(int a) {
  int r = 0;
  for (int i = 0; pri[i] <= a && i < prin; i++) {
    while (!(a % pri[i])) {
      a /= pri[i], r += vis[pri[i]];
    }
    if (a == 1) {
      break;
    }
  }
  if (a != 1) {
    r += *lower_bound(badp, badp + badpn, a) == a ? -1 : 1;
  }
  return r;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int gcd_tmp[5005];
int work() {
  int ori = 0, go_on = true;
  for (int i = 0; i < num; i++) {
    ori += get_score(val[i]);
  }
  while (val[0] != 1 && go_on) {
    go_on = false;
    gcd_tmp[0] = val[0];
    for (int i = 1; i < num; i++) {
      gcd_tmp[i] = gcd(gcd_tmp[i - 1], val[i]);
    }
    for (int i = num - 1; ~i; i--) {
      if (get_score(gcd_tmp[i]) < 0) {
        go_on = true;
        int v = get_score(gcd_tmp[i]);
        for (int j = i; ~j; j--) {
          val[j] /= gcd_tmp[i];
          ori -= v;
        }
        goto end;
      }
    }
  end:;
  }
  return ori;
}
int main() {
  pre();
  scanf("%d%d", &num, &badpn);
  for (int i = 0; i < num; i++) {
    scanf("%d", &val[i]);
  }
  for (int i = 0; i < badpn; i++) {
    scanf("%d", &badp[i]);
    if (badp[i] < 100005) {
      vis[badp[i]] = -1;
    }
  }
  sort(badp, badp + badpn);
  printf("%d\n", work());
  return 0;
}
