#include <bits/stdc++.h>
using namespace std;
struct Prime {
  int f[35000], p[35000], pidx;
  Prime() {}
  void Init() {
    pidx = 0;
    for (int i = 2; i < 35000; i++) {
      if (!f[i]) {
        p[pidx++] = i;
        for (int j = i; j < 35000; j += i) f[j] = 1;
      }
    }
    return;
  }
  void decompos(int x, vector<int>& E) {
    E.clear();
    for (int i = 0; i < pidx; i++) {
      while (x % p[i] == 0) {
        E.push_back(p[i]);
        x /= p[i];
      }
    }
    if (x != 1) E.push_back(x);
  }
};
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int a[5000 + 5];
map<int, int> bad;
int cal(vector<int>& E) {
  int ans = 0;
  for (int i = 0; i < E.size(); i++) {
    if (bad.find(E[i]) == bad.end())
      ans++;
    else
      ans--;
  }
  return ans;
}
int main() {
  int n, m;
  Prime* p = new Prime();
  p->Init();
  cin >> n >> m;
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < m; i++) {
    int b;
    scanf("%d", &b);
    bad[b] = 1;
  }
  for (int i = n - 1; i >= 0; i--) {
    int g = a[0];
    for (int j = 1; j <= i; j++) g = gcd(g, a[j]);
    vector<int> E;
    p->decompos(g, E);
    if (cal(E) < 0) {
      for (int j = 0; j <= i; j++) a[j] /= g;
    }
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    vector<int> E;
    p->decompos(a[i], E);
    res += cal(E);
  }
  cout << res << endl;
  return 0;
}
