min25筛可以解决1e8~1e11范围内的问题。
此代码求n以内的质数和
inline char gc(){static char ibuf[RLEN],*ib,*ob;(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));return (ib==ob)?EOF:*ib++;
}
#define gc getchar
inline ll read(){char ch=gc();ll res=0,f=1;while(!isdigit(ch))f^=ch=='-',ch=gc();while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();return f?res:-res;
}
ll poww(ll a,ll b,ll k)
{ll res=1;while(b){if(b&1) res=(res%k*a%k)%k;b/=2;a=(a%k*a%k)%k;}return res;
}
#define pb push_back
#define ll long long
#define cs const
#define re register
#define pii pair<ll,ll>
#define fi first
#define se second
#define db ll
ll mod;
inline ll add(ll a,ll b){return (a+=b)>=mod?a-mod:a;}
inline void Add(ll &a,ll b){(a+=b)>=mod?a-=mod:0;}
inline ll dec(ll a,ll b){return a>=b?a-=b:a-b+mod;}
inline void Dec(ll &a,ll b){(a-=b)<0?a+=mod:0;}
inline ll mul(ll a,ll b){return 1ll*a*b>=mod?1ll*a*b%mod:a*b;}
inline void Mul(ll &a,ll b){a=mul(a,b);}
inline ll ksm(ll a,ll b,ll res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(res=mul(res,a));return res;
}
cs ll N=1000006;
cs db eps=1e-10;
inline db C(ll x){return (ll)(x+1)*(ll)x/2;}
ll l,r;
ll f1[N],f2[N];
inline db query(ll k){if(!k)return 0;ll lim=sqrt(k);for(ll i=1;i<=lim;i++)f1[i]=C(i),f2[i]=C(k/i);for(ll p=2;p<=lim;p++){if(fabs(f1[p]-f1[p-1])<=eps)continue;cs ll xx=p;for(ll i=1;i<=lim/p;i++)f2[i]-=(f2[i*p]-f1[p-1])*xx;for(ll i=lim/p+1;1.0*p*p*i<=k&&i<=lim;i++)f2[i]-=(f1[k/i/p]-f1[p-1])*xx;for(ll i=lim;i>=1.0*p*p;i--)f1[i]-=(f1[i/p]-f1[p-1])*xx;}return f2[1];
}