#include <bits/stdc++.h>
using namespace std;
void setIO(string St) {
  string IN = St + ".in", OUT = St + ".out";
  freopen(IN.c_str(), "r", stdin);
  freopen(OUT.c_str(), "w", stdout);
}
bool NotPrime[50008];
int pn, Prime[50008];
map<int, bool> qz;
int N, M, A[5008], P[5008], Ans[5008];
void Init() {
  for (int i = 2; i <= 50000; i++)
    if (!NotPrime[i]) {
      Prime[++pn] = i;
      for (int j = i + i; j <= 50000; j += i) NotPrime[j] = 1;
    }
}
int Cut(int k) {
  int Ans = 0;
  for (int i = 1; i <= pn; i++) {
    if (Prime[i] > k) break;
    int n = 0;
    while (!(k % Prime[i])) {
      n++;
      k /= Prime[i];
    }
    if (n) Ans += n * (qz[Prime[i]] ? -1 : 1);
  }
  if (k > 1) Ans += (qz[k] ? -1 : 1);
  return Ans;
}
int gcd(int a, int b) { return (b ? gcd(b, a % b) : a); }
int main() {
  Init();
  scanf("%d%d", &N, &M);
  int Sum = 0;
  for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
  for (int i = 1; i <= M; i++) {
    int t;
    scanf("%d", &t);
    qz[t] = 1;
  }
  int g = A[1];
  for (int i = 1; i <= N; i++) {
    g = gcd(g, A[i]);
    Sum += Cut(A[i]);
    P[i] = Cut(g) * -1;
  }
  for (int i = N; i > 0; i--) {
    Ans[i] = -10000000;
    for (int j = N + 1; j > i; j--) {
      int t = Ans[j] + (P[i] - P[j]) * i;
      if (t > Ans[i]) Ans[i] = t;
    }
  }
  int Max = 0;
  for (int i = 1; i <= N; i++)
    if (Ans[i] > Max) Max = Ans[i];
  cout << Max + Sum << endl;
  return 0;
}
