prg42839

[programmers - 완전탐색] 소수 찾기

문제 풀이

이 문제는 만들 수 있는 숫자 찾기, 소수 판별하기 이렇게 2가지 문제를 해결하는 것으로 볼 수 있다.

만들 수 있는 숫자의 경우를 찾는 것은 재귀를 이용한 완전 탐색으로 풀면 된다.

소수 판별은 처음에 에라토스테네스의 체를 이용해 구현하려고 했으나, numbers가 길이 1 이상 7 이하인 문자열이므로 연산 횟수가 너무 늘어나는 문제가 생겼다. 단순히 for문을 돌며 mod 연산으로 풀면 O(n)의 시간 복잡도로 풀 수 있는데 말이다. 에라토스테네스의 체는 소수 판별할 수들의 범위가 너무 크지 않고, 대량의 소수들을 한 번에 판별해야 할 문제에서 쓰는 것이 좋을 것 같다.

소수 판별 O(n) -> O(n^(1/2))

단순한 소수 판별 알고리즘도 시간 복잡도를 O(n)에서 O(n^(1/2))으로 줄일 수 있다. 예를 들어, 8의 경우 2 * 4 = 4 * 2와 같은 식으로 대칭을 이루기 때문에 구하고자 하는 숫자의 제곱근까지만 약수의 여부를 검증하면 되겠다. 코드는 다음과 같다.

boolean isPrime(int n) {
    if (n == 0 || n == 1) return false;
    int end = (int) Math.sqrt(n);
    for (int i = 2; i <= end; i++) {
        if (n % i == 0) return false;
    }
    return true;
}