#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:100000000000000")
using namespace std;
int n, m, arr[5001];
set<int> mp;
map<int, int> dp;
int fact(int x) {
  if (dp[x] != 0) return dp[x];
  int tp = x;
  int k = 2, ret = 0;
  while (k * k <= x) {
    int cnt = 0;
    while (x % k == 0) {
      cnt++;
      x /= k;
    }
    if (cnt) {
      if (mp.find(k) != mp.end())
        ret -= cnt;
      else
        ret += cnt;
    }
    k++;
  }
  if (x > 1) {
    if (mp.find(x) != mp.end())
      ret--;
    else
      ret++;
  }
  return dp[tp] = ret;
}
int GCD(int a, int b) {
  if (b == 0) return a;
  return GCD(b, a % b);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  int x;
  for (int i = 0; i < n; i++) cin >> arr[i];
  for (int i = 0; i < m; i++) {
    cin >> x;
    mp.insert(x);
  }
  int ans = 0;
  for (int i = 0; i < n; i++) ans += fact(arr[i]);
  for (int i = 0; i < 31; i++) {
    int tmp = 0, g = arr[0], tot = ans, mx = 0, ind = -1, G;
    for (int i = 0; i < n; i++) {
      g = GCD(g, arr[i]);
      int tt = tot + (-fact(g)) * (i + 1);
      if (ind == -1)
        ind = i, mx = tt, G = g;
      else if (tt > tot)
        mx = tt, ind = i, G = g;
    }
    for (int i = 0; i < ind + 1; i++) arr[i] /= G;
    if (ans < mx)
      ans = mx;
    else
      break;
  }
  cout << ans << endl;
  return 0;
}
