#include <bits/stdc++.h>
using namespace std;
int m, n, a[100010], b[100010], x, sum = 0, mi = 0;
int gcd(int a, int b) {
  while (b) a %= b, swap(a, b);
  return a;
}
int count(int x) {
  int j = 2, k = 0, s = 0;
  while (j * j <= x) {
    while (j * j <= x && x % j) j++;
    if (x % j) break;
    int t = 0;
    while (x % j == 0) x /= j, t++;
    while (b[k] < j) k++;
    if (b[k] == j)
      s -= t;
    else
      s += t;
    j++;
  }
  if (x > 1) {
    while (b[k] < x) k++;
    if (b[k] == x)
      s--;
    else
      s++;
  }
  return s;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", a + i + 1);
  for (int i = 0; i < m; i++) scanf("%d", b + i);
  b[m] = 2147483647;
  for (int i = n; i >= 1; i--) {
    int d = 0;
    for (int j = 1; j <= i; j++) d = gcd(d, a[j]);
    if (count(d) < 0)
      for (int j = 1; j <= i; j++) a[j] /= d;
  }
  for (int i = 1; i <= n; i++) sum += count(a[i]);
  printf("%d\n", sum);
  return 0;
}
