#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,a[2010],b[105],g[2010];
bool vh[31623];
vector<int>prime;
inline void ini(){
	prime.reserve(3401);
	for(int i=2;i<=31622;++i){
		if(!vh[i]) prime.push_back(i);
		for(int j=0;j<prime.size()&&prime[j]*i<=31622;++j){
			vh[prime[j]*i]=true;
			if(i%prime[j]==0) break;
		}
	}
}inline int cal(int num){
	#define fir first
	#define sec second
	vector<pair<int,int>>spt;
	for(int i=0;i<prime.size()&&prime[i]*prime[i]<=num;++i){
		if(num%prime[i]==0) spt.push_back({prime[i],0});
		while(num%prime[i]==0) ++spt.back().sec,num/=prime[i];
	}if(num!=1) spt.push_back({num,1});
	num=0;int j=1;
	for(int i=0;i<spt.size();++i){
		while(j<=m&&b[j]<spt[i].fir) ++j;
		if(j<=m&&b[j]==spt[i].fir) num-=spt[i].sec;
		else num+=spt[i].sec;
	}return num;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ini();
	for(int i=1;i<=n;++i) cin>>a[i],g[i]=__gcd(g[i-1],a[i]);
	for(int i=1;i<=m;++i) cin>>b[i];
	int G=1,ans=0;
	for(int i=n;i>=1;--i){
		if(cal(g[i]/G)<0) G=g[i];
		ans+=cal(a[i]/G);
	}cout<<ans<<endl;
	return 0;
}