[Algorithm] 에라토스테네스의 채

1. 개요

소수(Prime Number)란 1과 자기자신만을 약수로 갖는 수이다. 에라토스테네스의 채를 이용하여 주어진 수가 소수인지 여부를 판별할 수 있다. 예제를 통해 에라토스테네스의 채의 동작방식에 대해 알아보도록 하자.

2. 예제

에라토스테네스의 채를 이용하여 1 ~ 100의 자연수에서 소수를 구해보자

1. 1은 소수가 아니므로 제외시킨다.

   

2. 다음 수인 2는 소수가 되고, 2를 제외한 2의 배수를 모두 지운다.

   

3. 다음 수인 3은 소수가 되고, 3을 제외한 3의 배수를 모두 지운다.

   

4. 다음 수인 5는 소수가 되고, 5를 제외한 5의 배수를 모두 지운다.

   

5. 다음 수인 7은 소수가 되고, 7을 제외한 7의 배수를 모두 지운다.

   

6. 다음 수인 11은 소수가 되고, 11을 제외한 11의 배수를 모두 지운다.

   

7. 다음 수인 13은 소수가 되고, 13을 제외한 13의 배수를 모두 지운다.

   

8. 다음 수인 17은 소수가 되고, 17을 제외한 17의 배수를 모두 지운다.

   

9. 다음 수인 19는 소수가 되고, 19를 제외한 19의 배수를 모두 지운다.

   

10. 다음 수인 23은 소수가 되고, 23을 제외한 23의 배수를 모두 지운다.

    

11. 다음 수인 29는 소수가 되고, 29를 제외한 29의 배수를 모두 지운다.

    

12. 다음 수인 31은 소수가 되고, 31을 제외한 31의 배수를 모두 지운다.

    

13. 다음 수인 37은 소수가 되고, 37을 제외한 37의 배수를 모두 지운다.

    

14. 다음 수인 41은 소수가 되고, 41을 제외한 41의 배수를 모두 지운다.

    

15. 다음 수인 43은 소수가 되고, 43을 제외한 43의 배수를 모두 지운다.

    

16. 다음 수인 47은 소수가 되고, 47을 제외한 47의 배수를 모두 지운다.

    

17. 다음 수인 53은 소수가 되고, 53을 제외한 53의 배수를 모두 지운다.

    

18. 다음 수인 59는 소수가 되고, 59를 제외한 59의 배수를 모두 지운다.

    

19. 다음 수인 61은 소수가 되고, 61을 제외한 61의 배수를 모두 지운다.

    

20. 다음 수인 67은 소수가 되고, 67을 제외한 67의 배수를 모두 지운다.

    

21. 다음 수인 71은 소수가 되고, 71을 제외한 71의 배수를 모두 지운다.

    

22. 다음 수인 73은 소수가 되고, 73을 제외한 73의 배수를 모두 지운다.

    

23. 다음 수인 79는 소수가 되고, 79를 제외한 79의 배수를 모두 지운다.

    

24. 다음 수인 83은 소수가 되고, 83을 제외한 83의 배수를 모두 지운다.

    

25. 다음 수인 89는 소수가 되고, 89를 제외한 89의 배수를 모두 지운다.

    

26. 다음 수인 97은 소수가 되고, 97을 제외한 97의 배수를 모두 지운다.

    

3. 구현 코드

3-1. C++

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/sieveOfEratosthenes.cpp

#include <iostream>

using namespace std;

int arr[103];

int main(void) {
    for(int i = 2; i <= 100; ++i) {
        if(!arr[i]) arr[i] = 1;
        for(int j = i * 2; j <= 100; j += i) {
            arr[j] = 2;
        }
    }

    for(int i = 2; i <= 100; ++i) {
        if(arr[i] == 1) cout << i << "\n";
    }
    return 0;
}

[실행 결과]

3-2. JAVA

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/sieveOfEratosthenes.java

public class SieveOfEratosthenes {

    static int arr[] = new int[103];

    public static void main(String[] args) {
        for(int i = 2; i <= 100; ++i) {
            if(arr[i] == 0) arr[i] = 1;
            for(int j = i * 2; j <= 100; j += i) {
                arr[j] = 2;
            }
        }
    
        for(int i = 2; i <= 100; ++i) {
            if(arr[i] == 1) System.out.println(i);
        }
    }
}

[실행 결과]