#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#define ll long long
using namespace std;
const int MN=5005,MM=40005;
ll n,m,a[MN],b[MN],g[MN],ans;
vector<ll> p;
map<ll,ll> mp,rem;
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
void init(){
    vector<ll> vis(MM);
    for(int i=2; i<MM; i++){
        if(!vis[i]) p.push_back(i);
        for(int j:p){
            if(i*j>MM) break;
            vis[i*j]=1;
            if(i%j==0) break;
        }
    }
}
ll f(ll x) {
	if(rem.count(x)) return rem[x];
	ll ret=0,y=x;
	for(int i:p){
		ll cnt=0;
		while(y%i==0) y/=i,cnt++;
		ret+=cnt*(mp[i]?-1:1);
		if(y==1) break;
	}
	if(y>1) ret+=(mp[y]?-1:1);
	return rem[x]=ret;
}
int main(){
    init();
    n=read();m=read();
    for(int i=1; i<=n; i++){a[i]=read();g[i]=gcd(g[i-1],a[i]);}
    for(int i=1; i<=m; i++){b[i]=read();mp[b[i]]=1;}
    for(int i=1; i<=n; i++) ans+=f(a[i]);
    for(int i=n,cnt=1,tmp; i; i--) if((tmp=f(g[i]/cnt))<0) ans-=tmp*i,cnt=g[i];
    write(ans);putchar('\n');
    return 0;
}