#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[6000];
int b[6000];
int x[6000];
map<int, bool> mp;
int bmm(int a, int b) {
  if (b > a) swap(a, b);
  if (b == 0) return a;
  return bmm(b, a % b);
}
int khar(int s) {
  int t = s;
  int sum = 0;
  for (int i = 2; i * i <= t; i++) {
    while (s % i == 0) {
      if (mp[i])
        sum--;
      else
        sum++;
      s /= i;
    }
  }
  if (s == 1) return sum;
  if (mp[s])
    sum--;
  else
    sum++;
  return sum;
}
int main() {
  cin >> n >> m;
  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int j = 0; j < m; j++) {
    cin >> b[j];
    mp[b[j]] = true;
  }
  for (int i = 0; i < n; i++) sum += khar(a[i]);
  x[0] = a[0];
  for (int i = 1; i < n; i++) x[i] = bmm(a[i], x[i - 1]);
  int v = 1;
  for (int i = n - 1; i >= 0; i--) {
    int p = khar(x[i] / v);
    if (p < 0) {
      sum -= (i + 1) * p;
      v = x[i];
    }
  }
  cout << sum << endl;
}
