#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
const int ST = 100010;
const int ST1 = 1000010;
const long long MOD = 1000000007;
long long ABS(long long a) {
  if (a < 0)
    return a * (-1);
  else
    return a;
}
int mas[ST];
int bad[ST];
int gds[ST];
vector<int> pr;
vector<bool> prime(ST, true);
void gen() {
  prime[0] = false;
  prime[1] = false;
  for (long long i = 2; i < ST; i++) {
    if (prime[i]) {
      for (long long j = i * i; j < ST; j += i) {
        prime[j] = false;
      }
      pr.push_back(i);
    }
  }
}
set<int> bb;
int gcd(int a, int b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
int raz(int ch) {
  int val = 0;
  for (int i = 0; i < (int)((pr).size()) && pr[i] <= ch; i++) {
    while (ch % pr[i] == 0) {
      ch /= pr[i];
      set<int>::iterator it = bb.find(pr[i]);
      if (it == bb.end())
        val++;
      else
        val--;
    }
  }
  if (ch != 1) {
    set<int>::iterator it = bb.find(ch);
    if (it == bb.end())
      val++;
    else
      val--;
  }
  return val;
}
int main() {
  int n, m;
  cin >> n >> m;
  gen();
  for (int i = 0; i < n; i++) {
    cin >> mas[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> bad[i];
    bb.insert(bad[i]);
  }
  int gd = mas[0];
  for (int i = 0; i < n; i++) {
    gd = gcd(gd, mas[i]);
    gds[i] = gd;
  }
  int need = 1;
  for (int i = n - 1; i >= 0; i--) {
    gds[i] /= need;
    int cur = raz(gds[i]);
    if (cur < 0) {
      need *= gds[i];
    }
    mas[i] /= need;
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int cur = raz(mas[i]);
    ans += cur;
  }
  cout << ans;
  return 0;
}
