#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mn=5005;
int n,m,a[mn],b[mn],ans,c[mn];
int prm[31630],tp;
bool vis[31630];
int gcd(int x,int y)
{
    return (y==0)?x:gcd(y,x%y);
}
void init()
{
    for(int i=2;i<31622;i++)
    {
        if(!vis[i])
        {
            prm[++tp]=i;
        }
        for(int j=1;j<=tp;j++)
        {
            if(i*prm[j]>31622)break;
            vis[i*prm[j]]=1;
            if(i%prm[j]==0)break;
        }
    }
}
signed main()
{
    init();
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&b[i]);
    }
    sort(b+1,b+m+1);
    for(int i=1;i<=n;i++)
    {
        int x=a[i];
        for(int tj=1;prm[tj]*prm[tj]<=a[i] && tj<=tp;tj++)
        {
            int j=prm[tj];
            if(x%j==0)
            {
                int ct;
                if(b[lower_bound(b+1,b+m+1,j)-b]==j)ct=-1;
                else ct=1;
                while(x%j==0)
                {
                    x/=j;
                    ans+=ct;
                }
            }
        }
        if(x!=1)
        {
            ans+=(b[lower_bound(b+1,b+m+1,x)-b]==x)?-1:1;
        }
        // cerr<<ans<<" "<<i<<'\n';
    }
    int x=0,ctt=1;
    for(int i=1;i<=n;i++)
    {
        if(gcd(x,a[i])!=x)
        {
            x=gcd(x,a[i]);
            int xx=x;
            ctt=0;
            for(int tj=1;prm[tj]*prm[tj]<=a[i] && tj<=tp;tj++)
            {
                int j=prm[tj];
                if(xx%j==0)
                {
                    int ct;
                    if(b[lower_bound(b+1,b+m+1,j)-b]==j)ct=-1;
                    else ct=1;
                    while(xx%j==0)
                    {
                        xx/=j;
                        ctt+=ct;
                    }
                }
            }
            if(xx!=1)
            {
                ctt+=(b[lower_bound(b+1,b+m+1,xx)-b]==xx)?-1:1;
            }
        }
        c[i]=ctt;
    }
    x=0;
    for(int i=n;i>=1;i--)
    {
        x=min(x,c[i]);
        ans-=x;
    }
    printf("%lld",ans);
}