[c++] 백준 4948 베르트랑 공준

백준 단계별로 풀어보기 [기본수학 2] 베르트랑 공준

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

4948번: 베르트랑 공준

 

[풀이]

이전에 했던 소수 판정식을 이용해서 풀면 시간초과가 나온다. 따라서 에라토스테네스의 체라는 소수판별에 최적화된 알고리즘을 이용하여 풀어야 했다. 에라토스테네스의 체는 소수를 판별할 범위까지 배열을 만든 다음, 특정 수의 배수에 해당하는 수를 계속 지워나가는 방법이다. 이때 자기자신은 제외하고 이미 지워진 수는 건너뛴다.

 

[코드]

#include <iostream>

int main() {
    int n, count;
    int arr[300000];

    while (true) {
        int count = 0;
        std::cin >> n;

        if (n == 0) break;

        for (int i = 0; i <= 2 * n; i++) {
            arr[i] = 1;
        }

	//에라토스테네스의 체
        for (int i = 2; i <= 2 * n; i++) {
            if (arr[i] == 0) continue;
            for (int j = 2 * i; j <= 2 * n; j += i) {
                arr[j] = 0;
            }
        }

        for (int i = n + 1; i <= 2 * n; i++) {
            if (arr[i] != 0)
                count++;
        }

        std::cout << count << std::endl;
    
    }
    return 0;
}