#include <bits/stdc++.h>
using namespace std;
int n, m, a[5010], b[5010], G[5010];
int gcd(int x, int y) {
  if (x == 0) return y;
  return gcd(y % x, x);
}
int val(int x) {
  int xx = x;
  int ret = 0;
  for (int i = 0; i < m; i++)
    while (xx % b[i] == 0) {
      ret--;
      xx /= b[i];
    }
  for (int i = 2; i * i <= xx; i++)
    while (xx % i == 0) {
      ret++;
      xx /= i;
    }
  if (xx > 1) ret++;
  return ret;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) cin >> b[i];
  int ans = 0;
  for (int i = 0; i < n; i++) ans += val(a[i]);
  for (int i = 0; i < n; i++) {
    G[i] = gcd(G[i - 1], a[i]);
  }
  int curr = 0;
  for (int i = n - 1; i >= 0; i--) {
    if ((-1) * val(G[i]) - curr > 0) {
      ans += (i + 1) * ((-1) * val(G[i]) - curr);
      curr = (-1) * val(G[i]);
    }
  }
  cout << ans;
  return 0;
}
