#include <bits/stdc++.h>
using namespace std;
map<int, int> ma;
int n, m;
int flag = 0, cnt = 0;
int a[5005], b[5005], zys[5005], zhi[1000005], v[5005], g[5005], val[1000005],
    prime[1000005];
int getval(int x) {
  int ans = 0;
  for (int i = 1; i <= cnt; i++) {
    while (x % prime[i] == 0) {
      x /= prime[i];
      ans += val[prime[i]];
    }
  }
  if (x > 1) {
    if (ma[x] == 1)
      ans--;
    else
      ans++;
  }
  return ans;
}
int zy(int x, int y) {
  if (x < y) swap(x, y);
  if (x % y == 0) return y;
  return zy(y, x % y);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) {
    scanf("%d", &b[i]);
    ma[b[i]] = 1;
  }
  zys[1] = a[1];
  for (int i = 2; i <= n; i++) zys[i] = zy(zys[i - 1], a[i]);
  val[1] = 0;
  for (int i = 2; i <= 100000; i++) {
    if (zhi[i] == 0) {
      prime[++cnt] = i;
      if (ma[i] == 1)
        val[i] = -1;
      else
        val[i] = 1;
      for (int j = i; (long long)i * j <= 100000; j++) {
        zhi[i * j] = 1;
      }
    }
  }
  int fuckans = 0;
  for (int i = 1; i <= n; i++) fuckans += getval(a[i]);
  for (int i = n; i >= 1; i--) {
    if (zys[i] > 0) {
      int d = getval(zys[i]);
      if (d < 0) {
        fuckans -= d * i;
        for (int j = 1; j <= i; j++) {
          zys[j] /= zys[i];
          a[j] /= zys[i];
        }
      }
    }
  }
  printf("%d\n", fuckans);
  return 0;
}
