[백준 1929번] 소수 구하기

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

소수의 특징은 약수가 자기 자신과 1만 있는 숫자니까 m, n을 입력을 받고, 자기 자신보다 작은 숫자를 다 나눠서 나머지가 0이 안나오는 걸로 판별을 했다

결과로 소수가 출력이 잘 되길래 제출했는 데, 시간 초과가 뜸

 

문제의 코드

#include <iostream>
using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;
    
    for(m; m <= n; m++){
        int p = m-1;
        while(p>1){
            if(m%p == 0){
                break;
            }
            p--;
        }
        if(p==1) cout << m << endl;
    }
}

검색을 해보니, 나같이 한 사람들은 다 시간 초과가 떴고 다양한 소수 판별법 (에라토스테네스의 체, 제곱근)을 사용해서 풀었더라

 

[백준] 1929번: 소수 구하기 - C++ (+ 에라토스테네스의 체) (tistory.com)

[백준] 1929번: 소수 구하기 - C++ (+ 에라토스테네스의 체)

 

분명 이대로 했는데 계속 시간 초과가 떴다

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;
    
    vector<int> arr(n+1, 0);
    
    for(int i=2; i<=n; i++){
        arr[i] = i;
    }
    
    for(int i=2; i*i <=n; i++){
        if(arr[i]==0) continue;
        for(int j = i*i; j<=n; j+=i){
            if(arr[j]==0) continue;
            else arr[j] = 0;
        }
    }
    
    for(int i=m; i<=n; i++){
        if(arr[i] != 0) cout << arr[i] << endl;
    }
    return 0;
}

 

[백준/C++] 1929번 : 소수 구하기(시간 초과, 에라토스테네스의 체) (tistory.com)

[백준/C++] 1929번 : 소수 구하기(시간 초과, 에라토스테네스의 체)

문제는 이 포스팅을 보고 찾았는 데, 마지막에 출력할 때 endl을 사용해서 그랬던 것

i*i 말고 i*2를 사용하라고도 되어 있다. 

enl는 버퍼를 flush하기 때문에 굉장히 느리게 작동된다고 한다. 그래서 "\n"을 사용하는 게 낫다고 한다.

 

그렇게 최종 수정한 코드는

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;
    
    vector<int> arr(n+1, 0);
    
    for(int i=2; i<=n; i++){
        arr[i] = i;
    }
    
    for(int i=2; i*i <=n; i++){
        if(arr[i]==0) continue;
        for(int j = 2*i; j<=n; j+=i){
            if(arr[j]==0) continue;
            else arr[j] = 0;
        }
    }
    
    for(int i=m; i<=n; i++){
        if(arr[i] != 0) cout << arr[i] << "\n";
    }
    return 0;
}