[BOJ-4948]베트르랑 공준

에라스토테네스 ​에라토스테네스의 체를 이용하여, 수가 소수인지 판별하고,

1~N 까지의 소수의 갯수를 저장하고 

답을 요구하는 것을 (N, 2*N] 까지 소수의 갯수를 요구하여 소수 갯수를 저장하는 num_of_prime을 만들어 문제를 풀이하였다.

#include<cstdio>
#include<vector>
 
using namespace std;
 
typedef vector<int> VI;
typedef vector<bool> VB;
 
const int SIZE = 444444;
VB is_prime; 
// true = prime
// false = not prime
VI num_of_prime;
 
void make_prime(){
    is_prime = VB(SIZE, true);
    num_of_prime = VI(SIZE, 0);
    // except 0, except 1
    for(int i = 2 ; i <= 333333 ; i++){
        if( (i == 2) || ((i%2) == 1) ){
            if(2*i > 333333) continue;
            for(int not_prime = i+i ; not_prime <= 333333 ; not_prime += i){
                is_prime[not_prime] = false;
            }
        }
    }
 
    int counting_prime = 0;
    for(int i = 1 ; i <= 333333 ; i++){
        if(is_prime[i]){
            counting_prime++;
        }
        num_of_prime[i] = counting_prime;
    }
}
 
int main(){
    make_prime();
    while(true){
        int input;
        scanf("%d", &input);
        if(input == 0) break;
        printf("%d\n",num_of_prime[2*input]-num_of_prime[input]);
    }
    return 0;
}