[Java] 소수 판별 - 에라토스테네스의 채

에라토스테네스의 채

 

- 채로 치듯이 수를 걸러내서 소수를 찾는 방법

- n이하의 소수를 모두 찾고 싶다면 1부터 n까지 쭉 나열한 다음에 2의 배수, 3의 배수, 5의 배수...로 계속해서 나누는 것

- 일종의 노가다 방식이긴 하지만, 소수를 생성하는 공식이 나오지 않았으므로 가장 빠른 방법

- 제곱근까지만 나눠주면 된다 (밑에 코드 참고)

 

소수 판별 코드 

    public static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        // 에라토스테네스 체
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

 

 

---

참고

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체