#include <bits/stdc++.h>
using namespace std;
const int inf = 100001;
inline int gcd(int x, int y) {
  if (!y) return x;
  return gcd(y, x % y);
}
unordered_set<int> s;
inline int beauty(int a) {
  int beauty = 0;
  int d = 2;
  while (a > 1 && a > d * d) {
    while ((a % d) == 0) {
      a /= d;
      if (s.count(d))
        beauty--;
      else
        beauty++;
    }
    d++;
  }
  if (a == d * d) {
    if (s.count(d))
      beauty -= 2;
    else
      beauty += 2;
  } else if (a > 1) {
    if (s.count(a))
      beauty--;
    else
      beauty++;
  }
  return beauty;
}
inline void solve() {
  int n, m;
  scanf("%d", &n), scanf("%d", &m);
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < m; i++) {
    int x;
    scanf("%d", &x);
    s.insert(x);
  }
  int req = 0;
  for (int j = n - 1; j >= 0; j--) {
    int g = a[0];
    for (int i = 0; i < j + 1; i++) {
      g = gcd(g, a[i]);
    }
    int b = beauty(g);
    if (b < 0) {
      for (int i = 0; i < j + 1; i++) {
        a[i] /= g;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans += beauty(a[i]);
  }
  cout << ans;
}
int main() {
  int t = 1;
  while (t--) solve();
  return 0;
}
