#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:10000000")
using namespace std;
int n, m, a[6000], b[6000], cur_f[6000];
int f(int x) {
  int answer = 0;
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) {
      int sign = -1;
      if (*lower_bound(b, b + m, i) != i) sign = 1;
      for (; x % i == 0; x /= i) answer += sign;
    };
  if (x > 1) {
    if (*lower_bound(b, b + m, x) != x)
      answer++;
    else
      answer--;
  };
  return answer;
};
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; };
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < m; i++) scanf("%d", &b[i]);
  long long answer = 0;
  for (int i = 1; i <= n; i++) {
    cur_f[i] = f(a[i]);
    answer += cur_f[i];
  };
  for (int i = n; i >= 1; i--) {
    int G = 0;
    for (int j = 1; j <= i; j++) G = gcd(G, a[j]);
    int Q = f(G);
    if (Q < 0) {
      answer -= Q * 1ll * i;
      for (int j = 1; j <= i; j++) a[j] /= G;
    };
  };
  cout << answer << endl;
  return 0;
};
