[백준 알고리즘] 1929 소수구하기 C++

문제 : https://www.acmicpc.net/problem/1929

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;

int main() {
    int M, N;
    cin >> M >> N;
    int array[N];
    
    for( int i = 0 ; i < N+1; i++){
        array[i] = 1;
    }
    
    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 = M ; i < N+1; i++){
        if(array[i] != 0)
        cout <<i<< "\n";
    }
    return 0;
}

성공한 사진 !

but... 계속해서 시간초과가 나왔다. 그 이유를 찾을 수 없어 끙끙 거렸는데 멋지신 분의 글을 보고 수정했더니 단번에 통과를 받았다 !!

나의 코드에서 시간초과의 원인은 바로....

" 6번 endl은 버퍼를 flush하기 때문에 너무 느립니다. '\n'을 대신 사용하세요. " 이었다. 만약 코드를 혼자 작성하고 결과값도 제대로 출력되는데 문제가 뭔지 모르겠다면 밑에 링크를 한번 방문해 확인해보는 것을 추천한다.

글 읽기 - ★☆★☆★ [필독] 소수 구하기 FAQ ★☆★☆★

 

https://www.acmicpc.net/board/view/39203