[Java] 소수 찾기 (programmers)

Haeun Noh·2023년 7월 19일

Java programmers 소수 찾기 에라토스테네스의 체

programmers

목록 보기

58/64

0719

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

n은 2이상 1000000이하의 자연수입니다.

입출력 예

`n`	`result`
`10`	`4`
`5`	`3`

입출력 예 설명

입출력 예 #1

1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

풀이 방식

이 문제는 앞서 풀었던 소수 만들기 문제의 상위 버전인 1~n사이의 소수의 개수를 찾는 문제입니다.

저는 소수 만들기 문제를 푼 직후에 이 문제를 풀었기 때문에

소수인지를 판별하는 메서드를 구현하고
소수라면 answer을 증가시키는 단계

까지는 어렵지 않게 작성할 수 있었습니다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for ( int i = 2; i <= n; ++i) {
            if ( isPrime(i) )
                ++answer;
        }
        
        return answer;
    }
    
    public boolean isPrime(int num) {
        for ( int i = 2; i <= num/2; i++) {
            if ( num % i == 0 ) {
                return false;
            }
        }
        return true;
    }
}

하지만 이내 런타임 에러 하나와 효율성 검사에서 막히게 되었습니다.

효율성 검사에서 막혔다는 말은 즉, 불필요한 for문이 돌아가고 있다는 소리였습니다.

전 이미 num/2로 for문의 반복을 반으로 줄였다고 생각했는데도 무언가 부족한 듯 보였습니다.

그리고 얼마 지나지 않아 저는 에라토스테네스의 체라는 알고리즘을 알게 되었습니다. 사실상 이 문제의 핵심입니다.

에라토스테네스의 체란?

고대 그리스의 수학자 에러토스테네스가 만들어낸 소수를 판별하는 알고리즘으로 소수를 대량으로 빠르고 정확하게 구하는 법입니다.

만약 1~100사이의 숫자 중 소수를 찾는다면?

먼저 1~100까지의 숫자를 나열합니다.
소수도 합성수도 아닌 유일한 자연수 1을 제거합니다.
2를 제외한 2의 배수를 제거합니다.
3을 제외한 3의 배수를 제거합니다.
4의 배수는 지울 필요가 없습니다. 이미 2의 배수에서 지워졌기 때문입니다.
5를 제외한 5의 배수를 제거합니다.
6의 배수는 지울 필요가 없습니다.2의 배수와 3의 배수에서 이미 지워졌기 때문입니다.
7을 제외한 7의 배수를 제거합니다.
이런 식으로 남은 것들의 2배수, 3배수를 지워나가면 다음과 같이 100이하의 소수가 남게 됩니다.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

이렇게 에라스토테네스의 체를 이용해 1~n까지의 소수를 알고싶다면 n까지 모든 수의 배수를 다 나눠볼 필요가 없습니다.

만약 n보다 작은 어떤 수 m이 m = ab라면 a와 b 중 적어도 하나는 n 제곱근 이하입니다.

즉, n보다 작은 합성수 m은 n 제곱근보다 작은 수의 배수만 체크해도 전부 지워지기 때문에 n 제곱근 이하의 수의 배수만 지우면 됩니다.

결론 - 1~n 사이의 소수를 구할 때는 n 제곱근까지만 for문을 돌려도 된다!

🚨(주의) 다만 에라토스테네스의 체는 특정 범위 내의 소수를 판정하는 데에만 효율적입니다.

만약 주어진 수 하나가 소수인가? 만을 따지는 상활이라면
이는 소수판정법이라고 해서 에라토스테네스의 체와는 비교도 안 되게 빠른 방법이 넘쳐납니다.

에라스토테네스의 체는 특정 범위 내의 소수를 판정하는 데에만 효율적이라는 점을 꼭 알고 있읍시다!

이렇게 에라스토테네스의 알고리즘을 일부 활용하여 해당 문제를 풀 수 있었습니다.
소스코드는 아래에 있습니다.

소스 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for ( int i = 2; i <= n; ++i) {
            if ( (i == 2 || i % 2 == 0) && (i == 3 || i % 3 == 0) )
                continue;
            if ( isPrime(i) )
                ++answer;
        }
        
        return answer;
    }
    
    public boolean isPrime(int num) {
        for ( int i = 2; i <= (int)Math.sqrt(num); i++) {
            if ( num % i == 0 ) {
                return false;
            }
        }
        return true;
    }
}