#include <bits/stdc++.h>
using namespace std;
inline void Boost() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
const int NMAX = 5005;
int n, m, dp[NMAX][NMAX], a[NMAX], b[NMAX], gcd[NMAX];
int _gcd_(int a, int b) {
  int r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
int f_ans(int x) {
  int i, cx = x, ans = 0;
  for (i = 2; i * i <= cx; i++) {
    while (cx % i == 0) {
      cx /= i;
      ans++;
    }
  }
  if (cx > 1) ans++;
  for (i = 1; i <= m; i++) {
    while (x % b[i] == 0) {
      x /= b[i];
      ans -= 2;
    }
  }
  return ans;
}
int main() {
  int i, j;
  cin >> n >> m;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    gcd[i] = _gcd_(gcd[i - 1], a[i]);
  }
  for (i = 1; i <= m; i++) cin >> b[i];
  int curr = 1, now, p;
  now = gcd[n] / curr;
  p = f_ans(now);
  if (p < 0) curr *= now;
  for (i = n; i >= 1; i--) {
    now = gcd[i] / curr;
    if (f_ans(now) < 0) curr *= now;
    a[i] /= curr;
  }
  int ans = 0;
  for (i = 1; i <= n; i++) ans += f_ans(a[i]);
  cout << ans;
  return 0;
}
