[백준 알고리즘 4948] 베르트랑 공준

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

4948번: 베르트랑 공준

풀이방법 : 해당 수의 제곱근까지만 나누어보는 것 && 에라토스테네스의 체 (백준 1929 소수구하기 문제와 동일)

 

에라토스테네스의 체를 사용해야 하는 이유는 시간초과 때문이다. 소수를 판별하기 위해서 이전의 수를 모두 나누어보는 것은 시간복잡도가 엄청나게 커지는 방법이기 때문이다. 

 

 

해당 수의 제곱근까지만 나누어보는 것:

쉽게 생각해보자. 예를 들어 18의 소수를 구하려고 한다. 1,2,3,4,5,6,7,8,...,18 -> 루트 18은 대략 4. xx이다.

만약 4(루트 18) 보다 큰 소인수가 있다면 이미 그 짝은 4보다 작은 수일 것이다. ex) (4보다 큰 소인수 == 6 )-> (6의 짝 == 3)

그러니 이미 순차적으로 i를 증가시키는 동안 이미 4보다 작은 수로(3으로) 나누어보았을 것이다.

 

 

에라토스테네스의 체:

이름부터 어려운 에라토스테네스...의 체... 원리는 easy하다. 이전에 든 예 18로 계속 진행을 해보겠다.

1,2,3,4,5,6,7,8,...,18 에서 일단 소수가 될 수 없는 1을 빼고, 다음 수인 2가 소수인지 판별한다.

2가 소수네 ? --> 2를 제외한 2의 배수 다 삭제 : 2,3,5,7,9,11,13,15,17

2 다음 수인 3이 소수인지 판별한다. 

3이 소수네 ? --> 3을 제외한 3의 배수 다 삭제 : 2,5,7,11,13,17

~~ 해서 18일 때까지 반복을 하면 된다. 

 

작성한 코드는 다음과 같다.

#include <iostream>
#include <math.h>
using namespace std;

void Count(int N){
    if(N == 0 ) return;
    int array[N];
    int count = 0;
    
    for( int i = 0 ; i < N+1; i++){
            array[i] = i;
        }
    array[1] = 0;
    for(int i = 2 ; i < sqrt(N+1); i++){
        if(array[i] >= 1){
            for(int k = i*i ; k < N+1; k = k+i){
                array[k] = 0;
            }
        }
    }
    for(int i = N/2+1 ; i < N+1; i++){
        if(array[i] >= 1){
            count ++;
        }
    }
    cout << count << "\n";
    return;
}

int main() {
    int N;
    while(1){
        cin >> N;
        Count(2*N);
        if( N == 0 ) break;
    }
    return 0;
}

성공한 사진 !