#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[5050], b[5050];
map<int, int> isbm;
const int INF = 0x3f3f3f3f;
bool isbad[111111];
bool vis[111111];
int prim[111111];
int f[5050];
int tgcd[5050];
int dp[5050][5050];
int pnum = 0;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
void getprime() {
  prim[pnum++] = 2;
  for (int i = 3; i < 111111; i += 2) {
    if (vis[i]) continue;
    prim[pnum++] = i;
    for (int j = i; j < 111111; j += i) vis[j] = true;
  }
}
int getf(int s) {
  if (s == 1) return 0;
  int i;
  for (i = 0; i < pnum; i++) {
    if (!(s % prim[i])) {
      if (isbad[prim[i]])
        return getf(s / prim[i]) - 1;
      else
        return getf(s / prim[i]) + 1;
    }
  }
  if (isbm.find(s) == isbm.end())
    return 1;
  else
    return -1;
}
int main() {
  getprime();
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    if (i == 0)
      tgcd[i] = a[i];
    else
      tgcd[i] = gcd(tgcd[i - 1], a[i]);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d", b + i);
    if (b[i] > 111111) {
      isbm[b[i]] = 1;
    } else
      isbad[b[i]] = true;
  }
  for (int i = 0; i < n; i++) f[i] = getf(tgcd[i]);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) dp[i][j] = -INF;
  dp[n - 1][n - 1] = 0;
  for (int i = 0; i < n; i++) dp[n - 1][n - 1] += getf(a[i]);
  int ans = dp[n - 1][n - 1];
  dp[n - 1][n - 1] -= f[n - 1] * n;
  for (int i = n - 2; i >= 0; i--) {
    for (int j = n - 1; j >= i; j--) {
      if (dp[i + 1][j] != -INF) {
        dp[i][j] = max(dp[i][j], dp[i + 1][j]);
        if (i < j)
          dp[i][i] =
              max(dp[i][i], dp[i + 1][j] + f[j] * (i + 1) - f[i] * (i + 1));
      } else
        dp[i][i] = max(dp[i][i], ans - f[i] * (i + 1));
    }
  }
  for (int i = 0; i < n; i++) {
    ans = max(ans, dp[0][i]);
  }
  cout << ans << endl;
  return 0;
}
