[알고리즘] 에라토스테네스의 체(소수 알고리즘)

• 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
• 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
• 자기 자신을 제외한 2의 배수를 모두 지운다.
• 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
• 자기 자신을 제외한 3의 배수를 모두 지운다.
• 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
• 자기 자신을 제외한 5의 배수를 모두 지운다.
• 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
• 자기 자신을 제외한 7의 배수를 모두 지운다.
• 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

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();
    }
    }