#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int N, M;
int A[5002], B[5002];
int D[5002], E[5002], F[5002];
int result;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int getDif(int x) {
  int resnow = 0;
  for (int i = 1; i <= M; ++i)
    while (x % B[i] == 0) {
      --resnow;
      x /= B[i];
    }
  for (int i = 2; i * i <= x; ++i)
    while (x % i == 0) {
      ++resnow;
      x /= i;
    }
  if (x != 1) ++resnow;
  return resnow;
}
int main() {
  cin.sync_with_stdio(false);
  cin >> N >> M;
  for (int i = 1; i <= N; ++i) cin >> A[i];
  for (int i = 1; i <= M; ++i) cin >> B[i];
  E[0] = 0;
  for (int i = 1; i <= N; ++i) {
    E[i] = gcd(E[i - 1], A[i]);
    F[i] = getDif(E[i]);
  }
  int base = 0;
  for (int i = 1; i <= N; ++i) base += getDif(A[i]);
  result = base;
  for (int i = N; i >= 1; --i) {
    D[i] = F[i] * i;
    for (int j = i + 1; j <= N; ++j) D[i] = min(D[i], D[j] + (F[i] - F[j]) * i);
    result = max(result, base - D[i]);
  }
  cout << result << '\n';
}
