#include <bits/stdc++.h>
using namespace std;
int N, M, a[5005], b[5005];
inline int CMMDC(int a, int b) {
  if (a == 1 || b == 1) return 1;
  int r = a % b;
  while (r) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
inline int Frum(int x) {
  int ans = 0, i, d;
  for (i = 1; i <= M && x > 1; ++i)
    while (x % b[i] == 0) {
      x /= b[i];
      --ans;
    }
  while (x % 2 == 0) {
    x /= 2;
    ++ans;
  }
  for (d = 3; d * d <= x && x > 1; d += 2)
    while (x % d == 0) {
      x /= d;
      ++ans;
    }
  if (x > 1) ++ans;
  return ans;
}
int main() {
  int i, j, frum = 0, cmmdc;
  cin >> N >> M;
  for (i = 1; i <= N; ++i) cin >> a[i];
  for (i = 1; i <= M; ++i) cin >> b[i];
  for (i = 1; i <= N; ++i) frum += Frum(a[i]);
  for (i = N; i; --i) {
    cmmdc = a[1];
    for (j = 2; j <= i; ++j) cmmdc = CMMDC(cmmdc, a[j]);
    if (Frum(cmmdc) < 0) {
      frum -= Frum(cmmdc) * i;
      for (j = 1; j <= i; ++j) a[j] /= cmmdc;
    }
  }
  cout << frum << "\n";
  return 0;
}
