#include <bits/stdc++.h>
using namespace std;
const int maxn = 5555;
int a[maxn], b[maxn], g[maxn], f, t1, t2;
int pri[111111], tot;
bool vis[111111];
map<int, int> mp;
void get_prime(int n) {
  int i, j;
  vis[1] = 1;
  tot = 0;
  for (i = 2; i <= n; i++) {
    if (!vis[i]) pri[++tot] = i;
    for (j = 1; j <= tot; j++) {
      if (pri[j] * i > n) break;
      vis[pri[j] * i] = 1;
      if (i % pri[j] == 0) break;
    }
  }
}
void Count(int n, int &x, int &y) {
  int i, j = 1;
  x = 0, y = 0;
  while (pri[j] * pri[j] <= n) {
    while (n % pri[j] == 0) {
      n /= pri[j];
      if (mp[pri[j]])
        y++;
      else
        x++;
    }
    j++;
  }
  if (n != 1) {
    if (mp[n])
      y++;
    else
      x++;
  }
}
int gcd(int a, int b) { return (b ? gcd(b, a % b) : a); }
int main() {
  int n, m, i, j, x, y;
  get_prime(100001);
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (i = 1; i <= m; i++) {
    scanf("%d", &b[i]);
    if (!mp.count(b[i])) mp[b[i]] = 1;
  }
  for (i = 1; i <= n; i++) {
    Count(a[i], x, y);
    t1 += x, t2 += y;
  }
  int ans = t1 - t2;
  g[1] = a[1];
  for (i = 2; i <= n; i++) g[i] = gcd(a[i], g[i - 1]);
  int p = n;
  f = 1;
  while (p) {
    g[p] /= f;
    Count(g[p], x, y);
    if (x < y) f *= g[p], ans += p * (y - x);
    p--;
  }
  printf("%d\n", ans);
  return 0;
}
