BOJ - 1929. 소수 구하기 (C++)

1929. 에라토스테네스의 체

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

[풀이]

일반적으로 n이 소수인지를 판별할 때 n을 2부터 n-1까지 나눈 나머지로 판별한다. 시간복잡도가 O(n)이다.

그러나 m과 n 사이의 소수를 판별할 때는 이중 반복문이 사용되어 O(n^2)이 된다.

 

n의 최대크기가 1,000,000정도로 커졌을 때 위와 같은 방식으로는 시간초과를 피할 수 없다. 그래서 에라토스테네스의 체라는 수학적 방법을 사용하게 되는데, 그냥 이게 더 빠르구나하고 외우고 활용하는게 좋을 것 같다.

 

우선 최대크기의 배열을 하나 잡는다. 나는 a[1000001]라고 잡았다.

1) 그리고 각 인덱스값을 값으로 할당해준다.

2) 2부터 n까지 돌며 해당 배열의 값 중에 '어떤 수의 배수'인 값만 0으로 만든다. (어떤 수의 배수인 값은 소수가 아니다) 0으로 만들어진 수는 소수가 아님을 의미한다. 이미 0인 수는 건너뛰고 0이 아닌 수의 배수들을 0으로 만든다.

3) 해당 배열에는 소수인 값은 자기 자신을 값으로 가지고 있고, 소수가 아닌 수는 0으로 초기화되어 있다.

    따라서 2부터 n까지 돌며 a[ ]가 0이 아닌 수가 소수이다.

#include <bits/stdc++.h>
using namespace std;
int a[1000001];

int main(){
    int m,n; cin >> m >> n;
    // 1)
    for (int i=2; i<=n; i++) a[i]=i;
    
    // 2)
    for (int i=2; i<=n; i++){
        if (a[i]==0) continue;
        for(int j=i+i; j<=n; j=j+i) a[j]=0;
    }
    
    // 3)
    for (int i=m; i<=n; i++) if (a[i]!=0) cout << i << '\n';
}