#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[5555], b[5555];
map<int, int> M;
int M2[111111];
int G[5555];
int calc(int n) {
  int t = n;
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    while (t % b[i] == 0) {
      t /= b[i];
      --ans;
    }
  }
  int q = sqrt(n + 1e-9);
  for (int x = 2; x <= q; ++x) {
    while (t % x == 0) {
      t /= x;
      ans++;
    }
    if (t == 1) break;
  }
  if (t > 1) {
    ans++;
  }
  return ans;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() {
  int ans = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d", &b[i]), M[b[i]] = 1;
    if (b[i] <= 100000) M2[b[i]] = 1;
  }
  for (int i = 1; i <= n; ++i) ans += calc(a[i]);
  G[1] = a[1];
  for (int i = 2; i <= n; ++i) G[i] = gcd(G[i - 1], a[i]);
  int gg = 1;
  for (int i = n; i >= 1; --i) {
    int tt = calc(G[i] / gg);
    if (tt < 0) {
      ans -= tt * i;
      gg = G[i];
    }
  }
  printf("%d\n", ans);
}
