#include <bits/stdc++.h>
using namespace std;
int dp[5010][5010], c[5010], a[5010];
bool v[5010][5010];
map<int, int> g, mp;
int f(int n) {
  if (n == 1) return 0;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      if (g[i])
        return f(n / i) - 1;
      else
        return f(n / i) + 1;
    }
  if (g[n]) return -1;
  return 1;
}
int fun(int n, int d) {
  if (n == 0) return max(0, f(a[n] / d));
  if (v[n][mp[d]]) return dp[n][mp[d]];
  v[n][mp[d]] = 1;
  int &ret = dp[n][mp[d]];
  if (d > 1) {
    ret = f(a[n] / d) + fun(n - 1, d);
    ret = max(ret, f(a[n] / c[n]) + fun(n - 1, c[n]));
  }
  if (d == 1) {
    ret = f(a[n]) + fun(n - 1, 1);
    if (c[n] > 1) ret = max(ret, f(a[n] / c[n]) + fun(n - 1, c[n]));
  }
  return ret;
}
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int main() {
  int i, j, T, k, n, m;
  while (~scanf("%d%d", &n, &m)) {
    for (i = 0; i < n; i++) {
      scanf("%d", &a[i]);
    }
    g.clear();
    mp.clear();
    for (i = 0; i < m; i++) {
      scanf("%d", &j);
      g[j] = 1;
    }
    int d = a[0], sz = 0;
    c[0] = d;
    mp[d] = ++sz;
    for (i = 1; i < n; i++) {
      d = c[i] = gcd(d, a[i]);
      if (!mp[d]) mp[d] = ++sz;
    }
    if (!mp[1]) mp[1] = ++sz;
    memset(v, 0, sizeof(v));
    int ans = fun(n - 1, 1);
    printf("%d\n", ans);
  }
  return 0;
}
