#include <bits/stdc++.h>
using namespace std;
const int N = 5100;
int n, m;
int a[N], g[N], pf[N], gf[N];
int b[N];
int dp[N];
inline int gcd(int x, int y) {
  while (x) {
    const int nx = y % x;
    const int ny = x;
    x = nx;
    y = ny;
  }
  return y;
}
inline int f(int x) {
  int ret = 0;
  int* j = b;
  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0) {
      j = lower_bound(j, b + m, i);
      int d = (j == b + m || *j != i ? 1 : -1);
      while (x % i == 0) {
        ret += d;
        x /= i;
      }
    }
  if (x != 1) {
    j = lower_bound(j, b + m, x);
    if (j == b + m || *j != x)
      ++ret;
    else
      --ret;
  }
  return ret;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  for (int i = 0; i < m; ++i) scanf("%d", b + i);
  sort(b, b + m);
  g[1] = a[1];
  gf[1] = pf[1] = f(a[1]);
  for (int i = 2; i <= n; ++i) {
    g[i] = gcd(g[i - 1], a[i]);
    pf[i] = pf[i - 1] + f(a[i]);
    if (g[i] == g[i - 1])
      gf[i] = gf[i - 1];
    else
      gf[i] = f(g[i]);
  }
  for (int i = n; i > 0; --i) {
    dp[i] = pf[n] - i * gf[i];
    for (int j = i + 1; j <= n; ++j)
      dp[i] = max(dp[i], dp[j] + i * gf[j] - i * gf[i]);
  }
  int ans = pf[n];
  for (int i = n; i > 0; --i) ans = max(ans, dp[i]);
  cout << ans << endl;
  return 0;
}
