AOJ 1172 Chebyshev’s Theorem

問題文: Chebyshev’s Theorem | Aizu Online Judge

素数やるだけ。エラトステネスとかしておく。

あと累積和作っておくと、(n,2n]に存在する素数が、O(1)で計算できる。正直必要ないけどなんとなく。

#include <iostream>
using namespace std;

int p[300001];

void init(int n){
	for(int i = 0 ; i <= 300000 ; i++)
		p[i] = 1;
	p[0] = p[1] = 0;
	
	for(int i = 2 ; i*i <= n ; i++)
		if(p[i] == 1)
			for(int j = i*i ; j <= n ; j += i)
				p[j] = 0;
}

int main(){
	init(300000);
	for(int i = 1 ; i <= 300000 ; i++)
		p[i] += p[i-1];
	int n;
	while(cin >> n , n){
		int ans = 0;
		cout << p[2*n] - p[n] << endl;
	}
}