#include <bits/stdc++.h>
typedef struct {
  int b, e;
} PFactor;
PFactor pFactor[5000][10];
int g[5000];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int pFactorize(int n, int idx) {
  int i;
  int cnt = 0;
  for (i = 2; i * i <= n; i++)
    if (n % i == 0) {
      int e = 0;
      do {
        e++;
        n /= i;
      } while (n % i == 0);
      pFactor[idx][cnt].b = i;
      pFactor[idx][cnt].e = e;
      cnt++;
    }
  if (n > 1) {
    pFactor[idx][cnt].b = n;
    pFactor[idx][cnt].e = 1;
    cnt++;
  }
  return cnt;
}
int binarySearch(int *data, int n, int key) {
  int l = 0, r = n - 1, m;
  while (l <= r) {
    m = (l + r) / 2;
    if (key == data[m])
      return 1;
    else if (key < data[m])
      r = m - 1;
    else
      l = m + 1;
  }
  return 0;
}
int main(void) {
  int i, j, k, l;
  int n, m, a[5000], b[5000], numPF[5000], max, hoge;
  scanf("%d %d", &n, &m);
  for (i = 0; i < n; i++) scanf("%d", a + i);
  for (i = 0; i < m; i++) scanf("%d", b + i);
  for (i = 0; i < n; i++) numPF[i] = pFactorize(a[i], i);
  max = 0;
  for (i = 0; i < n; i++)
    for (j = 0; j < numPF[i]; j++)
      max += binarySearch(b, m, pFactor[i][j].b) ? -pFactor[i][j].e
                                                 : pFactor[i][j].e;
  g[0] = a[0];
  for (i = 1; i < n; i++) g[i] = gcd(g[i - 1], a[i]);
  for (i = 0; i < n; i++) numPF[i] = pFactorize(g[i], i);
  hoge = 0;
  for (i = n - 1; i >= 0; i--) {
    int sum;
    sum = 0;
    for (j = 0; j < numPF[i]; j++)
      sum += binarySearch(b, m, pFactor[i][j].b) ? -pFactor[i][j].e
                                                 : pFactor[i][j].e;
    sum -= hoge;
    if (sum < 0) {
      hoge += sum;
      max -= (sum) * (i + 1);
    }
  }
  printf("%d\n", max);
  return 0;
}
