#include <bits/stdc++.h>
using namespace std;
bool comp[32000];
int P[32000];
int seive(int n, int* P) {
  int p, q, K = 0;
  comp[1] = true;
  char even = 1;
  for (p = 2; p * p <= n; p += 2) {
    if (!comp[p]) {
      for (q = p * p; q <= n; q += p * (2 - even)) comp[q] = true;
    }
    if (p == 2) --p, even = 0;
  }
  for (int i = (1); i <= (n); ++i)
    if (!comp[i]) P[K++] = i;
  return K;
}
int A[5005];
int B[5005];
int C[5005];
set<int> bad;
map<int, int> dp[5005];
int func[5005];
int N, M, K, H;
int g[5005];
map<int, int> cp_memo;
int compute(int n) {
  if (cp_memo.count(n)) return cp_memo[n];
  int orig = n;
  int ans = 0;
  for (int i = 0, p = P[i]; i < H && p * p <= n; ++i, p = P[i])
    while (!(n % p)) n /= p, ++ans;
  if (n > 1) ans++;
  n = orig;
  for (int i = 0, p = B[i]; i < M && p <= n; ++i, p = B[i])
    while (!(n % p)) n /= p, ans -= 2;
  return cp_memo[orig] = ans;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int solve(int n, int f) {
  if (n < 0) return 0;
  if (dp[n].count(f)) return dp[n][f];
  int& ans = dp[n][f];
  ans = solve(n - 1, f) + func[n] - compute(f);
  assert((g[n] % f) == 0);
  ans = max(ans, solve(n, g[n]));
  return ans;
}
int main() {
  H = seive(31700, P);
  cin >> N >> M;
  for (int i = 0; i < (N); ++i) scanf("%d", A + i);
  for (int j = 0; j < (M); ++j) scanf("%d", B + j);
  for (int j = 0; j < (M); ++j) bad.insert(B[j]);
  for (int i = 0; i < (N); ++i) func[i] = compute(A[i]);
  K = 0;
  for (int j = 0; j < (M); ++j) {
    if (A[0] % B[j]) continue;
    C[K++] = B[j];
  }
  g[0] = A[0];
  for (int i = (1); i <= (N - 1); ++i) g[i] = gcd(g[i - 1], A[i]);
  cout << solve(N - 1, 1) << endl;
}
