yukicoder : No.1661 Sum is Prime (Hard Version)

こちらも知らなかった…。
https://yukicoder.me/problems/no/1661

問題

整数区間[L,R]が指定される。
このうちの区間のうち、総和が素数となるのは何通りか。

初項X、項数N、公差1の数列の総和は、(X+X+N-1)*N/2である。
Nが3以上の場合、この値は合成数になる。
よって考えるのはN=1,2の時だけである。

π(x) := x以下の整数のうち素数の数
とする。

• N=1の時、条件を満たす組み合わせはπ(R)-π(L-1)である。
• N=2の時、条件を満たす組み合わせはπ(2*R)-π(2*L)である。
  • 実際は上限2*R-1だが、N=2ならRは2以上なので、2Rは合成数なので気にしなくてよい。

よって解はπ(2*R)-π(2*L)+π(R)-π(L-1)である。
あとはこのπ(x)を求めればよいわけだが、知らないアルゴリズムだったので下記サイトを参考に求めた。
眠れない夜は素数の個数でも数えましょう - えびちゃんの日記
Library Checker

ll L,R;

ll numprime(ll N) {
	if(N<=3) return max(0LL,N-1);
	ll sq=sqrt(N)+1;
	static vector<ll> small, large;
	small.resize(1+sq,0);
	large.resize(1+sq,0);
	ll i,j,p;
	for(i=1;i<=sq;i++) large[i]=N/i-1, small[i]=i-1;
	for(p=2;p<=sq;p++) {
		if(small[p]<=small[p-1]) continue;
		ll pc=small[p-1];
		ll q=p*p;
		for(i=1;i<=sq&&N/i>=q;i++) {
			ll ip=1LL*i*p;
			ll cur=(ip<=sq?large[ip]:small[N/ip])-pc;
			(i<=sq?large[i]:small[N/i])-=cur;
		}
		for(i=sq;i>=q;i--) small[i]-=small[i/p]-pc;
	}
	return large[1];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>R;
	
	ll ret=numprime(R)-numprime(L-1)+numprime(2*R)-numprime(2*L);
	cout<<ret<<endl;
}

まとめ

これ知らなかったけど、割と本番中の正答者多いんだよね。定番のアルゴリズムなのかな。
それとも、みな知らずに本番コピペとかでこなした？