[JAVA/알고리즘] 에라토스테네스의 체

에라토스테네스의 체

소수를 판별하는 알고리즘으로 소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위를 배열에 할당하고, 하나씩 지워나간다.

1~n 까지의 소수를 구한다면

1. n+1 크기의 배열을 생성 후 2부터 n까지의 정수를 넣는다. 

2. 반복문을 돌며 배열 값이 0인 i는 건너뛴다.

3. i=2 부터 시작하여 i의 배수에 해당하는 수를 모두 0으로 바꿔준다.

 

💡 자연수 n이 입력되면 1부터 n까지의 소수 출력하는 프로그램 작성

import java.util.*;

class Main {
    public static void main(String[] args) {
        Main T = new Main();
        Scanner s = new Scanner(System.in);

        int n = s.nextInt();
        int[] ch = new int[n+1];

        // 1. 배열을 생성하여 값 초기화 
        for(int i = 2; i<=n;i++){
            ch[i] = i;
        }

        // 2. 2부터 시작하여 특정 수의 배수에 해당하는 수는 모두 0으로.
        for (int i = 2; i <= n ; i++) {
            if (ch[i] == 0) continue;  // 이미 0인 수는 건너뛴다

            for (int j = i+i; j <= n ; j+=i) {
                ch[j] = 0; // i의 배수는 0으로
            }
        }

        // 3. 2부터 시작하여 배열 값이 0이 아닌 수 출력 
        for (int i = 2; i <= n ; i++) {
            if(ch[i] != 0)
                System.out.print(ch[i] + " ");
        }
    }
}

---

단일 숫자 소수 여부 확인

    public boolean isPrime(int num) {
        if (num == 1) return false;
        for (int i = 2; i <= Math.sqrt(num); i++)
            if (num % i == 0)
                return false;
        return true;
    }