#include <bits/stdc++.h>
using namespace std;
int a[5009];
int b[5009];
int p[100000], pr[100000];
int cnt = 0;
void prime(int n) {
  for (int i = 0; i < n; i++) p[i] = 1;
  p[0] = p[1] = 0;
  for (int i = 2; i * i < n; i++)
    if (p[i])
      for (int j = i * i; j < n; j += i) p[j] = 0;
  cnt = 0;
  for (int i = 2; i < n; i++)
    if (p[i]) pr[cnt++] = i;
}
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int g[5009];
int init(int n, int m) {
  int k = 0;
  for (int i = 0; pr[i] * pr[i] <= n; i++)
    if (n % pr[i] == 0) {
      int j = 0;
      while (n % pr[i] == 0) n /= pr[i], j++;
      if (binary_search(b, b + m, pr[i]))
        k -= j;
      else
        k += j;
    }
  if (n > 1) {
    if (binary_search(b, b + m, n))
      k -= 1;
    else
      k += 1;
  }
  return k;
}
int main() {
  int m, n;
  prime(100000);
  while (scanf("%d%d", &n, &m) != EOF) {
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);
    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
      g[0] = a[0];
      for (int j = 1; j <= i; j++) g[j] = gcd(g[j - 1], a[j]);
      if (init(g[i], m) <= 0)
        for (int j = 0; j <= i; j++) a[j] /= g[i];
    }
    for (int i = 0; i < n; i++) ans += init(a[i], m);
    printf("%d\n", ans);
  }
  return 0;
}
