#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T>
void chkmin(T &x, T y) {
  x = x > y ? y : x;
}
const int INF = (1ll << 30);
template <typename T>
void read(T &x) {
  x = 0;
  bool f = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = 0;
  } while (ch > '9' || ch < '0');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  x = f ? x : -x;
}
template <typename T>
void write(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 5000 + 5;
const int M = 1e5 + 7;
map<int, int> mp;
int n, m, ans, cnt, a[N], b[N], g[N], f[N], prime[M];
bool vis[M];
inline int gcd(int a, int b) {
  if (a < b) swap(a, b);
  return b == 0 ? a : gcd(b, a % b);
}
inline void init(int NN) {
  for (int i = 2; i <= NN; i++) {
    if (!vis[i]) {
      prime[++cnt] = i;
    }
    for (int j = 1; j <= cnt && prime[j] * i <= NN; j++) {
      vis[prime[j] * i] = true;
      if (i % prime[j] == 0) break;
    }
  }
}
inline int divide(int x) {
  if (mp.count(x)) return mp[x];
  int p = 0, tp = x;
  for (int i = 1; i <= m && b[i] <= x; i++) {
    while (x % b[i] == 0) x /= b[i], p--;
  }
  for (int i = 1; i <= cnt && 1ll * prime[i] * prime[i] <= x; i++) {
    while (x % prime[i] == 0) x /= prime[i], p++;
  }
  if (x != 1) p++;
  return mp[tp] = p;
}
int main() {
  read(n);
  read(m);
  for (int i = 1; i <= n; i++) read(a[i]), g[i] = gcd(a[i], g[i - 1]);
  for (int i = 1; i <= m; i++) read(b[i]);
  init(1e5);
  ans = 0;
  for (int i = 1; i <= n; i++) ans += divide(a[i]);
  for (int i = 1; i <= n; i++) f[i] = ans - i * divide(g[i]);
  for (int i = n; i >= 1; i--) {
    ans = max(ans, f[i]);
    for (int j = i - 1; j >= 1; j--) {
      int gg = g[j] / g[i];
      f[j] = max(f[j], f[i] - j * divide(gg));
      chkmax(ans, f[j]);
    }
  }
  printf("%d\n", ans);
  return 0;
}
