#include <bits/stdc++.h>
using namespace std;
const int N = 5100, M = 40000;
vector<int> p;
int P[M], a[N], b[N], n, m, t = 1, k, ans;
int gcd(int x, int y) { return (y == 0) ? x : gcd(y, x % y); }
int f(int x) {
  int ans = 0;
  for (int i = 0; i < m; i++)
    while (x % b[i] == 0) {
      ans--;
      x /= b[i];
    }
  for (int i = 0; i < p.size(); i++)
    while (x % p[i] == 0) {
      ans++;
      x /= p[i];
    }
  if (x != 1) ans++;
  return ans;
}
void work(int x, int g) {
  if (x == n) return;
  work(x + 1, gcd(g, a[x + 1]));
  int k = f(g / t) * (x + 1);
  if (k < 0) {
    ans -= k;
    t = g;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", a + i);
  for (int i = 0; i < m; i++) scanf("%d", b + i);
  for (int i = 2; i < M; i++) {
    if (P[i] == 0) {
      if (b[k] == i)
        k++;
      else
        p.push_back(i);
    }
    for (int j = 2; i * j < M; j++) P[i * j] = 1;
  }
  for (int i = 0; i < n; i++) ans += f(a[i]);
  work(0, a[0]);
  printf("%d\n", ans);
  return 0;
}
