#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[5050], b[5050], c[5050];
int pri[100010], cnt;
bool vis[100010];
int gcd(int a, int b) {
  while (a > 0 && b > 0) {
    if (a > b)
      a %= b;
    else
      b %= a;
  }
  return a + b;
}
void get_pri() {
  cnt = 0;
  memset(vis, 0, sizeof(vis));
  for (int i = 2; i <= 100000; i++) {
    if (!vis[i]) {
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt && i * pri[j] <= 100000; j++) {
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
    }
  }
}
int cal(int x) {
  int cnt = 0;
  for (int i = 0; i < m; i++) {
    while (x % b[i] == 0) {
      x /= b[i];
      cnt--;
    }
  }
  for (int i = 0; pri[i] * pri[i] <= x; i++) {
    while (x % pri[i] == 0) {
      x /= pri[i];
      cnt++;
    }
  }
  if (x > 1) cnt++;
  return cnt;
}
int main() {
  cin >> n >> m;
  get_pri();
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < m; i++) scanf("%d", &b[i]);
  for (int i = 0; i < n; i++) {
    if (i == 0)
      c[i] = a[i];
    else
      c[i] = gcd(c[i - 1], a[i]);
  }
  int now = 1;
  int ans = 0;
  for (int i = 0; i < n; i++) ans += cal(a[i]);
  for (int i = n - 1; i >= 0; i--) {
    if (cal(c[i] / now) < 0) {
      ans -= cal(c[i] / now) * (i + 1);
      now = c[i];
    }
  }
  printf("%d\n", ans);
}
