[백준] 4948 | 베르트랑 공준 | C++

풀이의 핵심은 이렇다.

 

i는 2부터 123456*2일 때까지 반복:
    j는 2부터 i*j값이 123456*2일 때까지 반복:
        i*j의 값은 소수가 아님을 배열에 저장한다;

(n이 입력으로 주어진다.)

i는 n+1부터 2*n까지 반복:
    저장한 배열의 값으로 소수인지 아닌지 판별한다:
        소수라면 count;

count한 소수의 갯수 출력(이후 다시 n을 입력으로 받고 반복실행);

 

소수가 아닌 수를 생각해보자면,

어떤 수의 2배, 3배, 4배, ..., n배는 모두 소수가 아니다.

 

따라서 어떤 수를 i로 생각하고, 2부터 반복으로 곱해나가서

그 값은 소수가 아니라고 저장하는 것이다.

(이 방식은 매우 자주 사용되므로 외우는 편이 낫다.)

 

정답 소스코드

#include <iostream>
using namespace std;

int main(void) {
    int arr[123456*2] = {0,};

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

    int n, cnt;

    while(1) {
        cin >> n;
        cnt = 0;

        if(n == 0) break;

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

        cout << cnt << endl;
    }

    return 0;
}

---

 

반복의 끝(2*123456)은 반복의 최소화를 위해 이렇게 설정한 것이다.