#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
int a[maxn], pg[maxn];
map<int, int> mp;
int n, m, b, ind;
int f(int x) {
  if (x == 1) return 0;
  ind = x;
  for (int i = 2; i * i <= x; i++) {
    if (x % i) continue;
    ind = i;
    break;
  }
  if (mp[ind]) return f(x / ind) - 1;
  return f(x / ind) + 1;
}
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int j = 1; j <= m; j++) {
    cin >> b;
    mp[b] = 1;
  }
  pg[1] = a[1];
  for (int i = 2; i <= n; i++) pg[i] = gcd(pg[i - 1], a[i]);
  for (int i = n; i >= 1; i--) {
    if (f(pg[i]) >= 0) continue;
    for (int j = 1; j <= i; j++) {
      a[j] /= pg[i];
      pg[j] /= pg[i];
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) ans += f(a[i]);
  cout << ans << endl;
  return 0;
}
