백준) 4948 베르트랑 공준 (에라토스테네스의 체)

베르트랑 공준

https://www.acmicpc.net/problem/4948

소수를 에라토스테네스의 체를 사용해 판별해야 한다.

백준 1978 소수 찾기    (https://www.acmicpc.net/problem/1978)

백준 1929 소수 구하기 (https://www.acmicpc.net/problem/1929)

와 풀이를 겸한다.

에라토스테네의 체는 N보다 작거나 같은 모든 소수를 구하는 알고리즘이다.

방법은 다음과 같다.

2부터 시작하면서, 2의 모든 배수를 거른다.(2는 제외하고)

걸러지지 않은 가장 작은 수부터, 배수를 거르는 위의 작업을 반복한다.

위의 알고리즘은 N번 루프를 돌면서 배수들을 거른다.

루프 한 번당 배수들은 몇 개나 걸려질까?

위키신이 이르시길(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity)

평균적으로 log (log n) 번 걸러진다 하신다. 따라서 이 알고리즘의 시간복잡도는 n * log(log n) 이다.

베르트랑 공준은 임의의 n에 대해 (n, 2n] 구간엔 반드시 소수가 존재한다는 주장이다.

이를 검증하기 위해 여러 n이 주어지며, 매 번 소수의 갯수를 리턴해야 한다.

n이 몇 번이나 주어질지 상세되어있지 않으므로, 이미 부분합을 구해놓자.

그러면 n마다 psum[2 * n] - psum[n] 으로 (n, 2n]구간의 소수의 갯수를 선형시간에 알아낼 수 있다.

#include <stdio.h>
 
#define maxn 246912
int t;
 
bool is_not_prime[maxn + 1] = { true,true,false };
int psum[maxn + 1];
 
int main() {
    for (int i = 2; i <= maxn; ++i) {
        if (is_not_prime[i])
            continue;
        for (int j = i + i; j <= maxn; j += i)
            is_not_prime[j] = true;
    }
 
    for (int i = 2; i <= maxn; ++i) {
        psum[i] = psum[i - 1];
        if (!is_not_prime[i])
            psum[i]++;
    }
 
    while (1) {
        scanf("%d", &t);
        if (t == 0)
            break;
 
        printf("%d\n", psum[t * 2] - psum[t]);
    }
 
    return 0;
}