백준 1929번 C언어 풀이 - 두번째 풀이

https://codejin.tistory.com/31

백준 1929번 C언어 풀이

이 문제를 풀고 난 후에, 에라토스테네스의 체 알고리즘이 더 효율적이라고 조언을 받았다. 그래서 이 알고리즘으로 다시 풀어보았다.

 

에라토스테네스의 체는 소수를 찾는 하나의 알고리즘인데, 2부터 시작하여, 2의 배수를 모두 지운다. 그리고 1을 더한 3의 배수들도 지운다. 또 1을 더하면 4가 되는데, 아까 2의 배수들이 모두 지워졌으므로, 무시하고 다시 1을 더한다. 이를 반복하여 지워지지 않은 숫자들의 배수를 모두 지워가면서 소수를 찾는 방법이다.

 

이를 적용하여 다음과 같이 다시 풀어보았다.

#include <stdio.h>
#include <stdbool.h>
#define SIZE 1000001

int main () {
    bool seive[SIZE] = {false, false}; // 0부터 시작 (0,1,2,3....), 0은 계산의 편의성을 위해 넣음, 1은 소수도 합성수도 아니므로 false
    int m,n;
    scanf("%d%d", &m, &n);

    for (int i = 2; i < SIZE; i++) {
        seive[i] = true; // 일단 2 이상의 모든 숫자들을 true로 초기화
    }
    for (int i = 2; i < SIZE; i++) {
        if (seive[i]) { // 만약 지워지지 않은 숫자라면
            for (int p = 2; p*i < SIZE; p++) {
                seive[i*p] = false; //그 배수들을 모두 지운다
            }
        }
    }

    for (int i = m; i <= n; i++) {
        if (seive[i]) printf("%d\n", i);
    }
    return 0;
}