#include <bits/stdc++.h>
using namespace std;
const int N = 5100;
const int oo = 1e9;
const int MX = 100000000;
const int FF = 33000;
int n, m, a[N], gc[N];
int dp[5010], pre[5010];
map<int, bool> bad;
map<int, int> cache;
vector<int> prime;
bool mark[FF + 200];
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int fact(int num) {
  if (cache.find(num) != cache.end()) return cache[num];
  int &ret = cache[num];
  long long idx = 0, pf = prime[0];
  while (pf * pf <= num) {
    int cnt = 0;
    while (num % pf == 0) num /= pf, cnt++;
    ret += cnt * (bad[pf] ? -1 : 1);
    if (++idx < prime.size()) pf = prime[idx];
  }
  if (num != 1) ret += bad[num] ? -1 : 1;
  return ret;
}
int eval() {
  int res = 0;
  for (int i = 0; i < n; ++i) res += fact(a[i]);
  return res;
}
int rn(int l, int r, int gc) {
  return pre[r] - (!l ? 0 : pre[l - 1]) - (r - l + 1) * fact(gc);
}
int calc(int idx) {
  if (idx == n) return 0;
  int &ret = dp[idx];
  if (ret != -oo) return ret;
  ret = rn(idx, n - 1, 1);
  for (int j = idx; j < n; ++j) {
    ret = max(ret, rn(idx, j, gc[j]) + calc(j + 1));
  }
  return ret;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int first, i = 0; i < m; ++i) {
    scanf("%d", &first);
    bad[first] = 1;
  }
  for (long long i = 2; i <= FF; ++i) {
    if (mark[i]) continue;
    for (int j = i; j <= FF; j += i) mark[j] = 1;
    prime.push_back(i);
  }
  for (int i = 0; i < n; ++i) gc[i] = !i ? a[i] : gcd(a[i], gc[i - 1]);
  for (int i = 0; i <= n; ++i) dp[i] = -oo;
  for (int i = 0; i < n; ++i) {
    pre[i] = fact(a[i]);
    if (i) pre[i] += pre[i - 1];
  }
  cout << calc(0) << endl;
  return 0;
}
