#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[5500], b[5500], g[5500];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
void init() {
  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);
  }
  g[1] = a[1];
  for (int i = 2; i <= n; i++) {
    g[i] = gcd(g[i - 1], a[i]);
  }
}
bool mark[100000];
int p[100000], cnt;
void init_prime() {
  memset(mark, true, sizeof(mark));
  cnt = 1;
  mark[2] = true;
  mark[1] = false;
  mark[0] = false;
  for (int i = 2; i < 100000; i++) {
    if (mark[i]) {
      p[cnt++] = i;
    }
    for (int j = 1; j <= cnt && i * p[j] <= 100000; j++) {
      mark[i * p[j]] = false;
    }
  }
}
int goodandbad(int h) {
  int res = 0;
  for (int i = 1; i <= m && h >= b[i]; ++i)
    while (h % b[i] == 0) {
      --res;
      h /= b[i];
    }
  for (int i = 1; i <= cnt && h >= p[i] * p[i]; ++i)
    while (h % p[i] == 0) {
      ++res;
      h /= p[i];
    }
  if (h > 1) ++res;
  return res;
}
int te(int x) {
  int ret = 0;
  for (int i = 0; i < cnt && p[i] * p[i] <= x; i++) {
    while (x % p[i] == 0) {
      x /= p[i];
      if (mark[p[i]])
        ret++;
      else
        ret--;
    }
  }
  if (x > 1)
    if (mark[x])
      ret++;
    else
      ret--;
  return ret;
}
void work() {
  int ans = 0, s = 1;
  for (int i = n; i >= 1; i--) {
    int tmp = 0;
    g[i] /= s;
    if (goodandbad(g[i]) <= 0) s *= g[i];
    tmp = goodandbad(a[i] / s);
    ans += tmp;
  }
  printf("%d\n", ans);
}
int main() {
  init();
  init_prime();
  work();
  return 0;
}
