#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
int n, m;
int a[5050], b[5050];
int g[5050];
map<int, int> de;
int gg[5050];
int F(int x) {
  int ans = 0;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int j = (int)(lower_bound(b, b + m, i) - b);
      int add = 0;
      if (b[j] == i)
        add = -1;
      else
        add = 1;
      while (x % i == 0) {
        x /= i;
        ans += add;
      }
    }
  }
  if (x > 1) {
    int j = (int)(lower_bound(b, b + m, x) - b);
    if (b[j] == x)
      ans--;
    else
      ans++;
  }
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d", &b[i]);
  }
  sort(b, b + m);
  for (int i = 0; i < n; i++) {
    gg[i] = (i == 0 ? a[i] : gcd(gg[i - 1], a[i]));
  }
  for (int i = n - 1; i >= 0; --i) {
    int g = gg[i];
    if (g == 1) {
      continue;
    }
    int delta = 0;
    if (de.count(g)) {
      delta = de[g];
    } else {
      delta = F(g);
    }
    de[g] = delta;
    g = gg[i];
    if (delta < 0) {
      for (int j = 0; j <= i; j++) {
        a[j] /= g;
        gg[j] /= g;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans = ans + F(a[i]);
  }
  cout << ans << endl;
  return 0;
}
