[알고리즘] 에라토스테네스의 체(소수 구하는 알고리즘) 자바 구현

[알고리즘] 에라토스테네스의 체(소수 구하는 알고리즘) 자바 구현

안녕하세요. 오늘은 소수를 찾는 방법인 '에라토스테네스의 체'라는 알고리즘에 대해 알아보겠습니다.

알고리즘 진행은 아래와 같습니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 2는 소수이므로 오른쪽에 2를 쓴다.

3. 자기 자신을 제외한 2의 배수를 모두 지운다.

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.

7. 자기 자신을 제외한 5의 배수를 모두 지운다.

8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.

9. 자기 자신을 제외한 7의 배수를 모두 지운다.

10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

(출처 : 위키백과)

결국 2부터 시작해서 해당 수가 소수이면 표시를 하고, 그 수의 배수들은 모두 소수 후보에서 제외한다는 것입니다.

소수는 1과 자기자신만이 약수인 수이니까요.

그럼 4, 6, 8 ... 이 지워졌고, 남은 수들 중 가장 작은 수 3을 확인합니다.

3은 소수입니다. 그럼 3을 소수라 표시하고 3의 배수들은 모두 후보에서 제외합니다.

또 다음. 4는 아까 2의 배수에서 지워졌으므로 남은 수들 중에서 다음은 5입니다.

5는 또 5 소수이죠.

슬슬 느낌이 오네요!

소수를 찾고나서 소수가 될 수 없는 수들을 지우고, 다음 소수를 찾고 하는 과정에서

지우고 난 다음 나오는 수는 바로 소수로 나오네요.

이러한 점들을 정리해보면,

2부터 N까지의 수 중에서 소수를 찾는다고 했을 때,

N의 제곱근(나누어 떨어지지 않는다면 보다 큰 자연수)보다 작은 소수의 배수를 모두 지우고 남는 수는 모두 소수입니다.

(이해..되셨나요?)

네..

암튼..ㅎㅎ

위키백과에 있는 짤로 보시면 이해가 쉬우실겁니다!

구현해보자면 아래와 같습니다.

public class Eratostenes {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        if(num <= 1) return;
 
        boolean[] arr = new boolean[num+1];    //true 이면 해당 인덱스 소수.
        arr[0] = arr[1] = false;
        for(int i=2; i<=num; i+=1) {
            arr[i] = true;
        }
 
        //2 부터 숫자를 키워가며 배수들을 제외(false 할당)
        for(int i=2; i*i<=num; i+=1) {
            for(int j=i*i; j<=num; j+=i) {
                arr[j] = false;        //2를 제외한 2의 배수 false
            }
        }
        System.out.println("Prime number list from 2 to " + num + " : ");
        for(int i=0; i<=num; i+=1) {
            if(true == arr[i]) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
    }
}
 

결과를 보면 소수만 걸러서 잘 나오는 것을 확인할 수 있습니다.

에라토스테네스의 체는 아무래도 단순 반복문으로 소수인지를 하나하나 판단하는 것보다

속도가 정말정말 빠릅니다..

비교해보시면 체감이 되실겁니다.

끝까지 읽어주셔서 감사합니다.

여러분들의 공감 클릭, 댓글 하나가 큰 힘이 됩니다!