#include <bits/stdc++.h>
using namespace std;
const int MAXP = 33 * 1000 + 10, MAXN = 5001;
bool prime[MAXP];
vector<int> prs;
int a[MAXN], b[MAXN], n, m;
set<int> bad;
inline int gcd(int x, int y) {
  if (x < y) swap(x, y);
  if (y == 0) return x;
  return gcd(y, x % y);
}
inline bool good(int x) { return !binary_search(b, b + m, x); }
inline int f(int x) {
  int ret = 0;
  for (int i = 0; i < prs.size(); i++) {
    int cur = prs[i], cntT = 0;
    while (x % cur == 0) {
      x /= cur;
      cntT++;
    }
    if (cntT) {
      if (good(cur))
        ret += cntT;
      else
        ret -= cntT;
    }
  }
  if (x > 1) {
    if (good(x))
      ret++;
    else
      ret--;
  }
  return ret;
}
int tmpGcd[MAXN];
int main() {
  ios::sync_with_stdio(false);
  for (int i = 2; i < MAXP; i++) {
    if (!prime[i]) {
      prs.push_back(i);
      for (long long j = i * i; j < MAXP; j += i) prime[j] = true;
    }
  }
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) cin >> b[i];
  tmpGcd[0] = a[0];
  for (int i = 1; i < n; i++) tmpGcd[i] = gcd(tmpGcd[i - 1], a[i]);
  int cur = 1, sum = 0;
  for (int i = 0; i < n; i++) sum += f(a[i]);
  for (int i = n - 1; i >= 0; i--) {
    int tmp = tmpGcd[i] / cur;
    if (f(tmp) < 0) {
      sum -= (i + 1) * f(tmp);
      cur *= tmp;
    }
  }
  cout << sum << endl;
  return 0;
}
