JArchive 프로그래밍 일기

문제

소수 구하기 백준 1929번

리뷰

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

에라토스테네스의 체 를 이용한 문제다.

소수의 배수들을 전부 지우는 것이 핵심이다.

2는 소수다. 2의 배수를 전부 지운다.

3은 소수다. 3의 배수를 전부 지운다.

4는 2의 배수이므로 이미 지워졌다. 지나간다.

5는 소수다. 5의 배수를 전부 지운다.

6은 2의 배수이므로 이미 지워졌다. 지나간다.

이것을 코드로 나타내면 다음과 같다.

처음에는 전부 소수라고 0으로 초기화된 배열을 만든다.

그리고 0과 1은 소수가 아니니까 1로 만든다.

int A[1000001] = { 0, };

A[0] = 1; // 0과 1은 소수가 아니다. 지운다. 
A[1] = 1;

반복문 i를 2부터 N까지 순회한다.

앞서 소수 찾기 문제 에서 배운대로 N까지의 소수를 구하려면 루트 N까지만 확인하면 된다.

for(int i = 2; i*i <= N; i++){

    if(A[i] == 0) {  // 소수 라면, 

        for(int j = i*i; j <= N; j+=i ){ // 소수 i의 배수들을 전부 지운다  
            A[j] = 1;  
        }
    }
}    

루트 i < = N 는 아래와 같다.

i <= N * N

양변을 제곱한다. i의 루트가 사라진다. N은 제곱이 된다.

루트는 실수니까 오차를 발생시킬 수 있으므로 이렇게 제곱을 이용해 실수 사용을 피하는 것이다.

j는 i의 제곱부터 시작한다.

그 이유는 아래를 다시 읽어보면 된다.

처음에 2의 배수들을 지우면서 소수들의 x 2 는 이미 지워졌다.

또 3이 소수니까. 소수들의 x3은 이미 지워졌다.

이런식으로 지우다 보면 자신의 제곱 부터 지우면 된다.

2는 소수다. 2의 배수를 전부 지운다. -> 2x2, 2x3, 2x4, 2x5 .... 를 지운다

3은 소수다. 3의 배수를 전부 지운다. -> 3x2는 이미 2의 배수 지울 때 지워졌다. 3x3 부터 지운다.

4 ( 2 x 2) 는 2의 배수이므로 이미 지워졌다. 지나간다.

5는 소수다. 5의 배수를 전부 지운다.

​ -> 5x2, 5x3, 5x4 는 이미 2의배수, 3의배수, 4의배수 지울 때 지워졌다. 5x5 부터 지운다.

6 ( 3 x 2 ) 은 2의 배수이므로 이미 지워졌다. 지나간다.

맞은 코드

#include <iostream> 
#include <algorithm>
using namespace std;

int M, N;
int A[1000001] = { 0, };

int main(void){

    cin >> M >> N;

    A[0] = 1; // 0과 1은 소수가 아니다. 지운다. 
    A[1] = 1;

    for(int i = 2; i*i <= N; i++){

        if(A[i] == 0) {  

            for(int j = i*i; j <= N; j+=i ){ // i의 배수들을 전부 지운다  
                A[j] = 1;  
            }
        }
    }    

    for(int i = M; i <= N; i++){ // 0 으로 남은 소수 출력  
        if(A[i] == 0) {
            printf("%d\n", i);
        }
    } 

    return 0;    
} 

백준 1929번 문제 질문게시판에서 다양한 방식으로 풀어나가는 글을 읽어보며 도움이 많이 됬다.
정수를 곱할 때 int 표현범위를 오버플로우 하지 않도록 주의해야 한다는 점도 배웠다.