#include <bits/stdc++.h>
using namespace std;
int composite[50000];
vector<int> primes;
void sieve() {
  for (int i = 2; i < sqrt(50000) + 1; i++) {
    if (composite[i]) continue;
    for (int j = i + i; j < 50000; j += i) {
      composite[j] = i;
    }
  }
}
long long gcd(long long m, long long n) {
  if (n == 0) return m;
  if (m == n)
    return m;
  else if (n > m)
    return gcd(n, m);
  else
    return gcd(n, m % n);
}
int main() {
  sieve();
  for (int i = 2; i < 40000; i++) {
    if (!composite[i]) primes.push_back(i);
  }
  int n, m;
  cin >> n >> m;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  set<int> bad;
  for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    bad.insert(x);
  }
  for (int k = 0; k < n; k++) {
    int ind = -1;
    int div = -1;
    int q = -1;
    for (int i = 0; i < n; i++) {
      if (i == 0)
        q = a[i];
      else {
        q = gcd(q, a[i]);
      }
      int x = q;
      int val = 0;
      for (int j = 0; j < primes.size(); j++) {
        while (x % primes[j] == 0) {
          x /= primes[j];
          if (bad.count(primes[j])) {
            val++;
          } else
            val--;
        }
      }
      if (x > 1) {
        if (bad.count(x)) {
          val++;
        } else
          val--;
      }
      if (val > 0) {
        ind = i;
        div = q;
      }
    }
    if (ind == -1) break;
    for (int i = 0; i <= ind; i++) {
      a[i] /= div;
    }
  }
  int beauty = 0;
  for (int t = 0; t < n; t++) {
    int x = a[t];
    for (int j = 0; j < primes.size(); j++) {
      while (x % primes[j] == 0) {
        x /= primes[j];
        if (bad.count(primes[j]))
          beauty--;
        else
          beauty++;
      }
    }
    if (x > 1) {
      if (bad.count(x))
        beauty--;
      else
        beauty++;
    }
  }
  cout << beauty << endl;
  return 0;
}
