#include <bits/stdc++.h>
using namespace std;
int n, m;
map<int, int> isBad;
int arr[5010], g[5010];
int gcd(int a, int b) { return (!b ? a : gcd(b, a % b)); }
int solve(int x) {
  int ret = 0;
  for (int i = 2; i * i <= x; ++i) {
    while (x % i == 0) {
      if (isBad[i])
        --ret;
      else
        ++ret;
      x /= i;
    }
  }
  if (x > 1) {
    if (isBad[x])
      --ret;
    else
      ++ret;
  }
  return ret;
}
int main() {
  scanf("%d", &n), scanf("%d", &m);
  for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
  g[0] = arr[0];
  for (int i = 0; i < n - 1; ++i) g[i + 1] = gcd(g[i], arr[i + 1]);
  for (int i = 0; i < m; ++i) {
    int v;
    scanf("%d", &v);
    isBad[v] = 1;
  }
  vector<int> pf;
  int tmp = arr[0];
  for (int i = 2; i * i <= tmp; ++i) {
    if (tmp % i) continue;
    pf.push_back(i);
    while (tmp % i == 0) tmp /= i;
  }
  if (tmp > 1) pf.push_back(tmp);
  int d = 1;
  for (int i = n - 1; i >= 0; --i) {
    int G = g[i] / d;
    int res = 0;
    for (int j = 0; j < pf.size(); ++j) {
      while (G % pf[j] == 0) {
        if (isBad[pf[j]])
          --res;
        else
          ++res;
        G /= pf[j];
      }
    }
    if (res < 0)
      arr[i] /= g[i], d = g[i];
    else
      arr[i] /= d;
  }
  int out = 0;
  for (int i = 0; i < n; ++i) out += solve(arr[i]);
  cout << out;
}
