#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int a[5005], b[5005];
int n, m;
int ty(int x) {
  int ret = 0;
  for (int j = 2; j * j <= x; j++) {
    while (x % j == 0) {
      if (mp[j])
        ret--;
      else
        ret++;
      x /= j;
    }
  }
  if (x > 1) {
    if (mp[x])
      ret--;
    else
      ret++;
  }
  return ret;
}
int main() {
  mp.clear();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  int x;
  for (int i = 1; i <= m; i++) {
    scanf("%d", &x);
    mp[x] = 1;
  }
  b[1] = a[1];
  for (int i = 2; i <= n; i++) b[i] = gcd(b[i - 1], a[i]);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j * j <= a[i]; j++) {
      while (a[i] % j == 0) {
        if (mp[j])
          ans--;
        else
          ans++;
        a[i] /= j;
      }
    }
    if (a[i] > 1) {
      if (mp[a[i]])
        ans--;
      else
        ans++;
    }
  }
  int tp = 1;
  for (int i = n; i >= 1; i--) {
    int f = ty(b[i] / tp);
    if (f < 0) {
      ans -= f * i;
      tp = b[i];
    }
  }
  printf("%d\n", ans);
  return 0;
}
