#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int upto = sqrt(1e9);
int a[40005], b[40005], g[40005];
bool comp[40005];
vector<int> primes;
set<int> bad;
map<int, int> pf[40005];
vector<pair<int, int> > v[40005];
int f(int idx) {
  map<int, int>::iterator it;
  int res = 0;
  for (it = pf[idx].begin(); it != pf[idx].end(); ++it) {
    if (bad.count(it->first))
      res -= it->second;
    else
      res += it->second;
  }
  return res;
}
int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
int main() {
  ios_base::sync_with_stdio(0);
  primes.push_back(2);
  for (int i = 3; i < upto; i += 2) {
    if (!comp[i]) {
      for (int j = i * i; j < upto; j += i) comp[j] = 1;
      primes.push_back(i);
    }
  }
  int n, m, cnt, tmp;
  while (cin >> n >> m) {
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      tmp = a[i];
      for (int j = 0; j < primes.size(); ++j) {
        if (tmp % primes[j] == 0) {
          cnt = 0;
          while (tmp % primes[j] == 0) {
            tmp /= primes[j];
            ++cnt;
          }
          pf[i][primes[j]] = cnt;
          if (tmp == 1) break;
        }
      }
      if (tmp != 1) pf[i][tmp] = 1;
    }
    for (int i = 0; i < m; ++i) {
      cin >> b[i];
      bad.insert(b[i]);
    }
    g[0] = a[0];
    g[1] = gcd(a[0], a[1]);
    for (int i = 2; i < n; ++i) g[i] = gcd(g[i - 1], a[i]);
    int ba, go, idx;
    while (1) {
      idx = -1;
      for (int i = 0; i < n; ++i) {
        if (g[i] == 1) break;
        v[i].clear();
        tmp = g[i];
        ba = go = 0;
        for (int j = 0; j < primes.size(); ++j) {
          if (tmp % primes[j] == 0) {
            cnt = 0;
            while (tmp % primes[j] == 0) {
              tmp /= primes[j];
              ++cnt;
            }
            v[i].push_back(make_pair(primes[j], cnt));
            if (bad.count(primes[j]))
              ba += cnt;
            else
              go += cnt;
            if (tmp == 1) break;
          }
        }
        if (tmp != 1) {
          if (bad.count(tmp))
            ++ba;
          else
            ++go;
        }
        if (ba > go) idx = i;
      }
      if (idx == -1)
        break;
      else {
        for (int i = 0; i <= idx; ++i) {
          a[i] /= g[idx];
          g[i] /= g[idx];
          for (int j = 0; j < v[idx].size(); ++j) {
            pf[i][v[idx][j].first] -= v[idx][j].second;
            assert(pf[i][v[idx][j].first] >= 0);
            if (!pf[i][v[idx][j].first]) pf[i].erase(v[idx][j].first);
          }
        }
      }
    }
    int res = 0;
    for (int i = 0; i < n; ++i) res += f(i);
    cout << res << "\n";
    for (int i = 0; i < n; ++i) {
      pf[i].clear();
      v[i].clear();
    }
    bad.clear();
  }
  return 0;
}
