#include <bits/stdc++.h>
using namespace std;
int a[1000 * 10], b[1000 * 10], g[1000 * 10], n, m, ans;
int f(int x) {
  int res = 0;
  for (int i = 1; i <= m; i++)
    while (x % b[i] == 0) {
      x /= b[i];
      res--;
    }
  for (int i = 2; i * i <= x; ++i)
    while (x % i == 0) {
      x /= i;
      res++;
    }
  if (x > 1) res++;
  return res;
}
int gcd(int a, int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
int main() {
  cin.tie();
  cout.tie();
  ios_base::sync_with_stdio(false);
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    g[i] = gcd(g[i - 1], a[i]);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d", b + i);
  }
  for (int i = n; i; --i) {
    if (f(g[i]) < 0) {
      for (int j = 1; j <= i; j++) {
        a[j] /= g[i];
        g[j] /= g[i];
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    ans += f(a[i]);
  }
  printf("%d\n", ans);
  return 0;
}
