BOJ)4948 베르트랑 공준

문제: icpc.me/4948

n~2n 사이의 소수의 개수를 출력하면 되는 문제이다.

에라토스테네스의 체로 소수들을 구해 준 뒤 파셜섬의 차를 구해주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
bool p[270000];
int s[270000];
int n;
int main() {
    p[0] = p[1] = true;
    for (int i = 2; i <= 270000; i++) {
        if (p[i])continue;
        for (int j = i + i; j <= 270000; j += i) {
            p[j] = true;
        }
    }
    for (int i = 2; i <= 270000; i++) {
        if (!p[i])s[i]++;
        s[i] += s[i - 1];
    }
    scanf("%d", &n);
    while (n) {
        printf("%d\n", s[2 * n] - s[n]);
        scanf("%d", &n);
    }
    return 0;
}