#include <bits/stdc++.h>
using namespace std;
int xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
int n, m;
int dem, s[int(1e5 + 100)];
bool fr[int(1e5 + 100)];
int b[int(1e5 + 100)], a[int(1e5 + 100)], g[int(1e5 + 100)];
long long gcd(long long a, long long b) {
  if (a == 0)
    return b;
  else
    return gcd(b % a, a);
}
int calc(int x) {
  int res = 0;
  for (int i = (1), _b = (m); i <= _b; i++)
    while (x % b[i] == 0) {
      res--;
      x /= b[i];
    }
  for (int i = (1), _b = (dem); i <= _b; i++)
    while (x % g[i] == 0) {
      res++;
      x /= g[i];
    }
  if (x != 1) res++;
  return res;
}
int main() {
  for (int i = (2), _b = (32000); i <= _b; i++)
    if (!fr[i]) {
      for (int j = (2), _b = (32000 / i); j <= _b; j++) fr[i * j] = true;
    }
  scanf("%d%d", &n, &m);
  for (int i = (1), _b = (n); i <= _b; i++) scanf("%d", &a[i]);
  for (int i = (1), _b = (m); i <= _b; i++) {
    scanf("%d", &b[i]);
    if (b[i] <= 32000) fr[b[i]] = true;
  }
  for (int i = (2), _b = (32000); i <= _b; i++)
    if (!fr[i]) {
      dem++;
      g[dem] = i;
    }
  for (int i = (n), _a = (1); i >= _a; i--) {
    int ucln = a[1];
    for (int j = (1), _b = (i); j <= _b; j++) ucln = gcd(ucln, a[j]);
    if (calc(ucln) < 0) {
      for (int j = (1), _b = (i); j <= _b; j++) a[j] /= ucln;
    }
  }
  int res = 0;
  for (int i = (1), _b = (n); i <= _b; i++) {
    res += calc(a[i]);
  }
  cout << res << endl;
}
