#include <bits/stdc++.h>
using namespace std;
int n, m, a[50009], g[50009];
map<int, bool> s;
int gcd(int x, int y) {
  if (x % y == 0) return y;
  return gcd(y, x % y);
}
int ct(int x) {
  int ans = 0;
  for (register int i = 2; i * i <= x; ++i)
    while (x % i == 0) {
      if (s[i])
        ans--;
      else
        ans++;
      x = x / i;
    }
  if (x != 1) {
    if (s[x])
      ans--;
    else
      ans++;
  }
  return ans;
}
int main() {
  int x, pre = 1, sum = 0, tmp;
  scanf("%d%d", &n, &m);
  for (register int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (register int i = 1; i <= m; ++i) {
    scanf("%d", &x);
    s[x] = 1;
  }
  g[1] = a[1];
  for (register int i = 2; i <= n; ++i) g[i] = gcd(g[i - 1], a[i]);
  for (register int i = n; i >= 1; --i) {
    sum += ct(a[i]);
    if ((tmp = ct(g[i] / pre)) < 0) {
      sum -= tmp * i;
      pre = g[i];
    }
  }
  printf("%d", sum);
  return 0;
}
