#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 5007;
const int MAXS = 40007;
int n, m;
int a[MAXN], b[MAXN];
bool isp[MAXS];
int prm[MAXS], kp;
void init();
void input();
void work();
int getval(int x) {
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    while (x % b[i] == 0) x /= b[i], --ans;
  }
  for (int i = 1; prm[i] * prm[i] <= x; ++i) {
    while (x % prm[i] == 0) x /= prm[i], ++ans;
  }
  if (x ^ 1) ++ans;
  return ans;
}
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int main() {
  init();
  input();
  work();
}
void init() {
  ios::sync_with_stdio(false);
  memset(isp, true, sizeof(isp));
  isp[0] = isp[1] = false;
  for (int i = 2; i < MAXS; ++i) {
    if (isp[i]) {
      prm[++kp] = i;
      for (int j = i << 1; j < MAXS; j += i) isp[j] = false;
    }
  }
}
void input() {
  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]);
}
void work() {
  for (int i = n; i > 0; --i) {
    int g = a[1];
    for (int j = 2; j <= i; ++j) g = gcd(g, a[j]);
    if (getval(g) < 0) {
      for (int j = 1; j <= i; ++j) a[j] /= g;
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) ans += getval(a[i]);
  cout << ans << endl;
}
