#include <bits/stdc++.h>
using namespace std;
int prm;
int prime[100100];
int sieve[100100];
void calSieve() {
  sieve[1] = 1;
  for (int i = 2; i <= 200; i++) {
    int u = i;
    while (u + i <= 40000) {
      u = u + i;
      sieve[u] = 1;
    }
  }
  for (int i = 2; i <= 40000; i++) {
    if (sieve[i] == 0) {
      prm++;
      prime[prm] = i;
    }
  }
}
int A[5050];
int T[5050];
int n;
int m;
int arr[5050];
int prr[5050];
unordered_map<int, int> mp;
int getGCD(int a, int b) {
  if (b == 0) return a;
  return getGCD(b, a % b);
}
int getVal(int val) {
  int sum = 0;
  for (int i = 1; i <= prm; i++) {
    if (val % prime[i] == 0) {
      val = val / prime[i];
      if (mp[prime[i]] == 1)
        sum--;
      else
        sum++;
      i--;
    }
    if (val < prime[i]) break;
  }
  if (val != 1) {
    if (mp[val] == 1)
      sum--;
    else
      sum++;
  }
  return sum;
}
vector<int> vec;
void reduceVal() {
  int gcd = 0;
  arr[n + 1] = 1;
  for (int i = 1; i <= n + 1; i++) {
    int uu = getGCD(gcd, arr[i]);
    if (uu == 1) {
      vec.push_back(i - 1);
      break;
    }
    if (gcd != uu) {
      vec.push_back(i - 1);
    }
    gcd = uu;
  }
  for (int i = vec.size() - 1; i >= 1; i--) {
    gcd = 0;
    for (int j = 1; j <= vec[i]; j++) {
      gcd = getGCD(gcd, arr[j]);
    }
    if (getVal(gcd) < 0) {
      for (int j = 1; j <= vec[i]; j++) {
        arr[j] = arr[j] / gcd;
      }
    }
  }
}
int cal() {
  reduceVal();
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    ans = ans + getVal(arr[i]);
  }
  return ans;
}
int main() {
  calSieve();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &arr[i]);
    T[i] = arr[i];
    A[i] = 1;
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d", &prr[i]);
    mp[prr[i]] = 1;
  }
  printf("%d\n", cal());
  return 0;
}
