🎇 에라토스테네스 체

소수(Prime number)

• 1보다 큰 자연수 중 1과 자기 자신만을 인수로 갖는 자연수입니다.
• 반댓말은 '합성수'입니다.

에라토스테네스의 체

• 소수를 판별하는 알고리즘 입니다.
• 빠르고 대량으로 소수를 구할때 유리합니다.
• 시간 복잡도 : O(Nlog(logN))
  • 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 일어나기 때문입니다.

에라토스테네스의 체 원리

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다.
2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이 때 처음으로 선택된 숫자는 지우지 않습니다.
3. 배열의 끝까지 2번 과정을 반복한 후 배열에서 남아 있는 모든 수를 출력합니다.

• 어떤 N이 두 개이상의 곱으로 나타낼 수 있을 때, 인수 중 하나 이상은 반드시 √N보다 작거나 같다.

구현 로직

import java.util.Arrays;

public class Example {
    

    static int number = 100;

    public static void main(String[] args){
    
        /*
         * 100 이하의 모든 소수 찾기
         */
        boolean[] isPrime = new boolean[number+1]; // 배열 생성 및 초기화
        Arrays.fill(isPrime,true);

        isPrime[0] = isPrime[1] = false;
        
        // 2부터 number까지의 수의 배수에 해당하는 수를 모두 지운다.
        // 지울 때, number의 인수 중 하나는 number의 제곱근 보다 항상 작다는 것을 생각하자
        for(int i=2; i <= Math.sqrt(number); i++){
            if(!isPrime[i]) continue; // 이미 false인 값 건너뛰기
            
            // 자신을 제외한 배수 false 대입
            for(int j = i*2; j <= number; j += i){
                isPrime[j] = false;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 2; i < isPrime.length; i++){
            if(isPrime[i]){
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
    }
}