#include <bits/stdc++.h>
using namespace std;
int a[5111];
int gcda[5111];
set<int> b;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int beauty(int n) {
  int ans = 0;
  int h;
  for (int i = 2; i * i <= n; ++i) {
    h = 0;
    while (n % i == 0) {
      ++h;
      n /= i;
    }
    if (h) {
      if (b.count(i))
        ans -= h;
      else
        ans += h;
    }
  }
  if (n != 1) {
    if (b.count(n))
      ans--;
    else
      ans++;
  }
  return ans;
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < (n); ++i) cin >> a[i];
  int bad;
  for (int i = 0; i < (m); ++i) {
    cin >> bad;
    b.insert(bad);
  }
  int ans = 0;
  for (int i = 0; i < (n); ++i) ans += beauty(a[i]);
  gcda[0] = a[0];
  for (int i = (1); i <= (n - 1); ++i) gcda[i] = gcd(gcda[i - 1], a[i]);
  int bg, cgcd = 1;
  for (int i = n - 1; i >= 0; i--) {
    bg = beauty(gcda[i] / cgcd);
    if (bg < 0) {
      ans -= bg * (i + 1);
      cgcd = gcda[i];
    }
  }
  cout << ans << "\n";
  return 0;
}
