#include <bits/stdc++.h>
using namespace std;
template <typename T>
istream& operator>>(std::istream& in, vector<T>& a) {
  for (auto& it : a) in >> it;
  return in;
}
template <typename T1, typename T2>
istream& operator>>(std::istream& in, pair<T1, T2>& a) {
  in >> a.first >> a.second;
  return in;
}
template <typename T>
ostream& operator<<(std::ostream& out, vector<T>& a) {
  for (auto it : a) {
    out << " " << it;
  }
  out << endl;
  return out;
}
template <typename T1, typename T2>
ostream& operator<<(std::ostream& out, pair<T1, T2>& a) {
  out << a.first << ' ' << a.second;
  return out;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int n, m;
int check(int x, vector<int>& bad) {
  int ret = 0;
  for (int i = 0; i < m; i++)
    while (!(x % bad[i])) ret--, x /= bad[i];
  while (!(x & 1)) ret++, x >>= 1;
  for (int i = 3; i * i <= x; i += 2)
    while (!(x % i)) ret++, x /= i;
  if (x - 1) ret++;
  return ret;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  vector<int> a(n);
  cin >> a;
  vector<int> b(m);
  cin >> b;
  int ans = 0;
  for (int i = 0; i < n; i++) ans += check(a[i], b);
  for (int i = 0; i < n; i++) {
    int GCD = 0;
    for (int j = 0; j < n - i; j++) GCD = gcd(GCD, a[j]);
    int win = check(GCD, b);
    if (win < 0) {
      for (int j = 0; j < n - i; j++) a[j] /= GCD;
      ans -= win * (n - i);
    }
  }
  cout << ans << endl;
}
