#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:100000000000000")
using namespace std;
const int INF = 2e9;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
vector<pair<int, int> > fact[6000];
set<int> bad;
void me(int a, int id) {
  for (int i = 2; i * i <= a; i++) {
    while (a % i == 0) {
      fact[id].push_back(make_pair(i, bad.count(i) ? -1 : 1));
      a /= i;
    }
    if (a == 1) break;
  }
  if (a > 1) fact[id].push_back(make_pair(a, bad.count(a) ? -1 : 1));
}
int func(int a, int id) {
  int cur = 0;
  for (int i = (int)(fact[id]).size() - 1; i >= 0; i--) {
    if (a == 1) break;
    if (a % fact[id][i].first == 0) {
      a /= fact[id][i].first;
      cur += fact[id][i].second;
    }
  }
  return cur;
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> f(n);
  for (int i = 0; i < (n); i++) {
    scanf("%d", &f[i]);
  }
  for (int i = 0; i < (m); i++) {
    int a;
    scanf("%d", &a);
    bad.insert(a);
  }
  int best = 0, val = 0;
  for (int i = 0; i < n; i++) {
    me(f[i], i);
    val += func(f[i], i);
  }
  best = val;
  val = 0;
  for (int i = n - 1; i >= 0; i--) {
    int gc = 0;
    int temp = val;
    for (int j = 0; j <= i; j++) {
      gc = gcd(f[j], gc);
    }
    if (gc > 1) {
      for (int j = 0; j <= i; j++) {
        temp += func(f[j] / gc, j);
      }
      if (temp > best) {
        best = temp;
        for (int j = 0; j <= i; j++) {
          f[j] /= gc;
        }
      }
    }
    val += func(f[i], i);
  }
  cout << best;
}
