#include <bits/stdc++.h>
using namespace std;
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
int n;
int m;
int a[5000];
int b[5000];
int ff[5000];
int f[5001];
int sum[5001];
map<int, bool> bad;
int gcd(int a, int b) {
  while (a > 0 and b > 0)
    if (a > b)
      a %= b;
    else
      b %= a;
  return a + b;
}
int get(int x) {
  int res = 0;
  for (int i = 2; i * i <= x; ++i)
    while (x % i == 0) {
      if (bad[i])
        res -= 1;
      else
        res += 1;
      x /= i;
    }
  if (x > 1) {
    if (bad[x])
      res -= 1;
    else
      res += 1;
  }
  return res;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; ++i) scanf("%d", a + i);
  for (int i = 0; i < m; ++i) scanf("%d", b + i);
  for (int i = 0; i < m; ++i) bad[b[i]] = true;
  for (int i = 0; i < n; ++i) ff[i] = get(a[i]);
  sum[n] = 0;
  for (int i = n - 1; i >= 0; --i) sum[i] = sum[i + 1] + ff[i];
  f[0] = 0;
  int g = 0, ans = sum[0];
  for (int i = 0; i < n; ++i) {
    g = gcd(g, a[i]);
    int cur = get(g), add = 0;
    f[i + 1] = -1e9;
    for (int j = i; j >= 0; --j) {
      add += ff[j] - cur;
      f[i + 1] = max(f[i + 1], f[j] + add);
    }
    ans = max(ans, f[i + 1] + sum[i + 1]);
  }
  printf("%d\n", ans);
  return 0;
}
