#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 3;
long long a[maxn], dp[maxn], primes[maxn], g[maxn], res;
set<long long> b;
int f(int num) {
  if (num == 1) return 0;
  for (int i = 2; i * i <= num; i++)
    if (num % i == 0) {
      if (b.find(i) != b.end())
        return f(num / i) - 1;
      else
        return f(num / i) + 1;
    }
  if (b.find(num) != b.end())
    return -1;
  else
    return 1;
}
int gcd(int mini, int maxi) {
  if (mini == 0) return maxi;
  return gcd(maxi % mini, mini);
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) {
    long long in;
    cin >> in;
    b.insert(in);
  }
  for (int i = 0; i < n; i++) {
    if (i == 0) {
      g[i] = a[i];
      continue;
    }
    g[i] = gcd(g[i - 1], a[i]);
  }
  for (int i = 0; i < n; i++) res += f(a[i]);
  for (int i = n - 1; i >= 0; i--) {
    if (i == n - 1) {
      dp[i] = res - f(g[i]) * (i + 1);
      continue;
    }
    dp[i] = max({dp[i + 1], res - f(g[i]) * (i + 1),
                 dp[i + 1] - f(g[i] / g[i + 1]) * (i + 1)});
    if (dp[i] == dp[i + 1]) g[i] = g[i + 1];
  }
  cout << max(dp[0], res);
}
