[Java] 에라토스테네스의 체 - 소수 판별

[에라토스테네스의 체] 

- 가장 대표적인 소수 판별 알고리즘. 소수(Prime)이란 양의 약수를 1과 자기자신만 가지고 있는 자연수.

- 대량의 소수를 빠르게 구하는 방법

 

* 일반적인 소수 판별 코드 (시간 복잡도: O(N))

boolean isPrime(int x) {
	for (int i=2; i < x; i++) {
    	if (x % i == 0) {
        	return false;
        }
     }
     return true;
}

 

[에레토스테네스의 체 동작 방식]

ex) 1~25에서 소수 판별 

1. 소수를 판별하고자하는 범위 크기의 배열을 정의하고 숫자들을 배열에 넣어준다. 

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지워준다. 

    단, 자기자신은 지우지 않는다. 

 

- 2의 배수를 지운 모습, 자기자신은 지우지 않음.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

- 3의 배수도 지운 모습

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

3. 이미 지워진 숫자의 경우 그냥 건너뛴다. 4는 2의 배수를 지울 때 이미 지워졌으므로 건너뛴다. 

4. 위와 같은 동작을 25까지 동작하면 소수만 남게 된다. 

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

[JAVA code]

package com.algorithm.baekjoon.study;

public class SieveofEratosthenes {
    public static void main(String[] args) {
        int num = 25;
        printPrimeNumber(num);
    }

    public static void printPrimeNumber(int num) {

        // 배열에 원소 삽입
        int[] array = new int[num + 1];
        for (int i = 2; i <= num; i++) {
            array[i] = i;
        }
        
        for (int i = 2; i <= num; i++) {
            // 배열이 이미 0이면 건너뜀
            if (array[i] == 0) {
                continue;
            }

            // i의 배수인 원소들을 모두 지워줌 
            for (int j = i * i; j <= num; j += i) {
                array[j] = 0;
            }
        }

        // 0이 아닌(지워지지 않은) 숫자들만 출력 
        for (int i = 0; i < array.length; i++) {
            if (array[i] != 0) {
                System.out.print(array[i] + " ");
            }
        }
    }
}