소수 찾기

에라토스테네스의 체

수학자 에라토스테네스가 발견한 소수를 찾는 방법을 일컫는다.
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);
            }
        }
    }
}