#include <bits/stdc++.h>
int const maxn = 5500;
int const max_num = 32000;
int not_prime[max_num];
int bad_prime[maxn];
int good_prime[maxn];
int prefix_gcd[maxn];
int a[maxn], b[maxn];
int n, m, tot;
std::unordered_set<int> is_bad;
void init() {
  for (int i = 2; i < max_num; i++)
    if (!not_prime[i]) {
      if (is_bad.find(i) == is_bad.end()) good_prime[tot++] = i;
      for (int j = 2 * i; j < max_num; j += i) not_prime[j] = true;
    }
}
int gcd(int x, int y) { return (!y) ? x : gcd(y, x % y); }
int calc(int x, int t, int& common) {
  int count = 0, tx = x;
  for (int i = 0; i < m; i++)
    for (; !(x % bad_prime[i]); x /= bad_prime[i]) count++;
  for (int i = 0; i < tot; i++)
    for (; !(x % good_prime[i]); x /= good_prime[i]) count--;
  if (x > 1) count--;
  if (count > 0) common *= tx;
  return std::max(0, count * t);
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin >> n >> m;
  for (int i = 0; i < n; i++) std::cin >> a[i];
  for (int i = 0; i < m; i++) {
    std::cin >> bad_prime[i];
    is_bad.insert(bad_prime[i]);
  }
  init();
  for (int i = 0; i < n; i++) b[i] = a[i];
  int ans = 0;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      int count = 0;
      for (; !(b[j] % bad_prime[i]); b[j] /= bad_prime[i]) count++;
      ans -= count;
    }
  }
  for (int i = 0; i < n; i++) {
    int count = 0;
    for (int j = 0; j < tot; j++) {
      for (; !(b[i] % good_prime[j]); b[i] /= good_prime[j]) count++;
    }
    if (b[i] > 1) count++;
    ans += count;
  }
  prefix_gcd[0] = a[0];
  for (int i = 1; i < n; i++) prefix_gcd[i] = gcd(prefix_gcd[i - 1], a[i]);
  int common = 1;
  for (int i = n - 1; i >= 0; i--) {
    prefix_gcd[i] /= common;
    ans += calc(prefix_gcd[i], i + 1, common);
  }
  std::cout << ans << '\n';
}
