소수 찾기

NOTE

특정 백준/프로그래머스 문제에 종속되지 않은 일반 이론 정리 노트입니다. 소수 판별의 대표 알고리즘인 에라토스테네스의 체 개념과 구현을 다룹니다. 실전 적용 예시는 아래 관련 문서(DFS 순열+시행 나눗셈 비교, 백준 2023번)를 참고하세요.

에라토스테네스의 체

수학자 에라토스테네스가 발견한 소수를 찾는 방법을 일컫는다.
2,3,5,7을 제외한 해당 수의 배수를 제거하면, 소수인 숫자를 찾을 수 있다.

에라토스테네스의 체 과정

1. 한 자리 수의 소수 인 경우는 2,3,5,7이다. 해당 수의 경우에는 소수이므로 따로 저장
2. 2의 배수를 가지는 수는 소수가 아니므로 모두 제거
3. 3의 배수를 가지는 수는 소수가 아니므로 모두 제거
4. 5의 배수를 가지는 수는 소수가 아니므로 모두 제거
5. 7의 배수를 가지는 수는 소수가 아니므로 모두 제거
6. 위의 과정에서 2,3,5,7를 제외한 해당수의 배수가 아닌 수를 구함
7. 해당 숫자들이 소수

구현

public class App {
 
    public static void main(String[] args) throws Exception {
        int size = 1000;
        boolean[] decimalCheck = new boolean[size];
        
        for (int i = 2; i< size; i++){
            decimalCheck[i] = true;
        }
        validate(decimalCheck);
        PrintArray(decimalCheck);
 
    }
 
    private static void validate(boolean[] decimalCheck){
        
        for(int i = 2; i * i < decimalCheck.length; i++){
            if (decimalCheck[i]){
                for(int j = i*i; j < decimalCheck.length; j+=i){
                    decimalCheck[j] = false;
                }
            }
        }
        
    }
 
    private static void PrintArray(boolean[] decimalCheck){
        for (int i =2; i < decimalCheck.length; i++){
            if (decimalCheck[i]){
                System.out.println(i);
            }
        }
    }
}

---

🔗 관련

• (Algorithm) 소수찾기 - 핵심 개념 및 특징 정리 — 소수 판별 방식 비교(에라토스테네스의 체 vs DFS 순열+시행 나눗셈)
• (DFS) 백준 2023번 — 소수 판별(시행 나눗셈) 응용 문제