#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
int a[MAXN], p[MAXN], m, n, score[MAXN], g[MAXN], scoreg[MAXN];
int good_calc(int x) {
  int result = 0;
  for (int div = 2; div * div <= x; div++) {
    while (x % div == 0) {
      result++;
      x /= div;
    }
  }
  if (x != 1) {
    result++;
  }
  return result;
}
int calc(int x) {
  int result = 0;
  for (int i = 0; i < m && p[i] <= x; i++) {
    while (x % p[i] == 0) {
      result--;
      x /= p[i];
    }
  }
  return result + good_calc(x);
}
int gcd(int a, int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) cin >> p[i];
  for (int i = 0; i < n; i++) {
    score[i] = calc(a[i]);
    g[i] = (i == 0 ? a[i] : gcd(g[i - 1], a[i]));
    scoreg[i] = calc(g[i]);
  }
  for (int i = n - 1; i >= 0; i--) {
    if (scoreg[i] < 0) {
      for (int j = 0; j <= i; j++) {
        g[j] /= g[i];
        score[j] -= scoreg[i];
        scoreg[j] -= scoreg[i];
      }
    }
  }
  int result = 0;
  for (int i = 0; i < n; i++) {
    result += score[i];
  }
  cout << result;
}
