[Algorithm] BAEKJOON 1929 - 소수 구하기 C++(시간 초과 해결)

[BAEKJOON] 1929번 소수 구하기

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

출처 : [wikipedia] 에라토스테네스의 체

2부터 차례대로 소수를 구하게 되면 시간 초과 결과와 마주하게된다. 이를 해결하기 위해서는 에라토스테네스의 체를 이용해야한다. 에라토스테네스의 체는 특정 범위가 주어졌을 때 그 범위 내의 소수를 찾는 빠르고 쉬운 방법이다.

Input

3 6

Output

3 5 7 11 13

Code

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
    int min, max;
    cin >> min>>max;


    bool arr[max];
    arr[0] = arr[1] = false;

    for(int i=2; i<=max; i++)
        arr[i] = true;


    for(int i=2; i*i <= max; i++){
        if(!arr[i]) continue;
        for(int j = i*2; j <= max; j += i) arr[j]=false;
    }

    for(int i=min; i<=max; i++)
        if(arr[i]) cout<<i<<'\n';

    return 0;
}

---

시행착오

처음에는 1434 문제와 비슷한 맥락으로 무작정 소수를 구하는 코드를 작성했다. 그 결과는 어김없이 시간 초과 라는 결과를 마주했다.

$^1$첫번째 시도

#include <iostream>
#include <cmath>

using namespace std;

bool isPrime(long long n)
{
    for(int i=2; i<=sqrt(n); i++)
            if(n%i == 0) return false;

    return true;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
    long long min, max;
    cin >> min>>max;

    for(int i=min; i<=max; i++){
        while(isPrime(i)){
            cout << i << endl;
            i++;
        }  
    }

    return 0;
}

$^2$두번째 시도

wikipedia에서 제공해주는 C++ 코드 기반으로 소수 구하기 코드를 작성했더니 어김없이 마주친 시간 초과 OTL..

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
    int min, max;
    cin >> min>>max;

    bool arr[max];
    arr[0] = arr[1] = false;

    for(int i=2; i<=max; i++)
        arr[i] = true;

    for(int i=2; i*i <= max; i++){
        if(!arr[i]) continue;
        for(int j = i*i; j <= max; j += i) arr[j]=false;
    }

    for(int i=min; i<=max; i++) if(arr[i]) cout<<i<<endl;
      
    return 0;
}

$^3$세번째 시도

사실 스스로의 힘으로 풀어보고 싶어서 여러번 도전 끝에 10번의 시간 초과 결과를 받고 다른 사람들의 코드를 찾아보기 시작했다. 그러다 ★한 줄기 빛☆ 같은 글을 발견하였다.

5. 에라토스테네스의 체를 구현할 때 흔히 안쪽 루프를 int j = i * i로 시작하는데, 
이렇게 하면 i가 46341이 되는 순간부터 
i * i가 int의 범위를 초과하기 때문에 오버플로우가 발생합니다. 
long long을 사용하거나, i * i 대신 i * 2부터 시작하는 등의 방법을 사용하세요.

이 글을 믿고 i*i 대신 i*2 로 시작하는 코드로 수정했더니 마법처럼 시간 초과의 저주가 풀렸다!

...생략
        
    for(int i=2; i*i <= max; i++){
        if(!arr[i]) continue;
        for(int j = i*2; j <= max; j += i) arr[j]=false;
    }

...

그리고 같은 글에서 앞으로의 코드 스타일에 변화를 주는 문장을 만났다. "추가로 endl은 버퍼를 flush하기 때문에 너무 느립니다. \n을 대신 사용하세요." 지금부터 endl을 내주고 '\n'를 취한다!