#include <bits/stdc++.h>
using namespace std;
const int NMax = 5100, MMax = 100000;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int N, M, A[NMax], B[NMax], P[MMax], P1[MMax], L;
int G[NMax], V[NMax], dp[NMax];
map<int, int> bad;
vector<pair<int, int> > Fac1;
pair<int, int> C[NMax];
int main() {
  P[1] = 1;
  for (int i = 2; i <= 40000; i++)
    if (!P[i]) {
      P1[L++] = i;
      for (int j = i * 2; j <= 40000; j += i) P[j] = 1;
    }
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; i++) scanf("%d", A + i);
  for (int i = 1; i <= M; i++) scanf("%d", B + i), bad[B[i]] = 1;
  int ret = 0, tmp = A[1];
  for (int i = 1; i <= N; i++) {
    int t = A[i], first = 0;
    for (int j = 0; j < L; j++)
      if (t % P1[j] == 0) {
        int x1 = 0;
        while (t % P1[j] == 0) {
          x1++;
          t /= P1[j];
        }
        if (bad[P1[j]])
          first -= x1;
        else
          first += x1;
      }
    if (t > 1) {
      if (bad[t])
        first--;
      else
        first++;
    }
    ret += first;
  }
  G[0] = A[1];
  int most = N + 1;
  if (A[1] == 1) {
    printf("%d\n", ret);
    return 0;
  }
  for (int i = 1; i <= N; i++) {
    G[i] = gcd(G[i - 1], A[i]);
    if (G[i] == 1) {
      most = i;
      break;
    }
    int t = G[i];
    for (int j = 0; j < L; j++)
      if (t % P1[j] == 0) {
        int x1 = 0;
        while (t % P1[j] == 0) {
          x1++;
          t /= P1[j];
        }
        if (bad[P1[j]])
          C[i].second += x1;
        else
          C[i].first += x1;
      }
    if (t > 1) {
      if (bad[t])
        C[i].second++;
      else
        C[i].first++;
    }
  }
  int ans = 0;
  for (int i = most - 1; i >= 1; i--) {
    dp[i] = (C[i].first - C[i].second) * i;
    for (int j = i + 1; j < most; j++)
      dp[i] = min(
          dp[i],
          dp[j] + (C[i].first - C[j].first - C[i].second + C[j].second) * i);
    if (dp[i] > 0) dp[i] = 1000000000;
    ans = min(ans, dp[i]);
  }
  printf("%d\n", ret - ans);
  return 0;
}
