[TIL #5] 소수 만들기

숫자를 담은 배열이 주어지고,

그 배열에서 3개를 뽑아 소수를 몇 개나 만들 수 있는지 확인하는 문제다.

 

소수는 약수가 자기 자신과 1 뿐인 수를 말한다.

번거로운 계산 과정 없이 바로 판단할 수 있는 건 다음과 같다.

• 1 이하인 수
• 2, 3, 5, 7, ....

하지만 숫자가 매우 크다면?

한눈에 판단하기 매우 어려울 것이다.

이를 판별하기 위한 여러 가지 방법이 있다.

 

1. 소수

1. 에라토스테네스의 체

소수 판별을 위한 가장 심플한 방법으로 에라토스테네스의 체가 있다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

정말 단순하고 시간 복잡도도 $O(n log log n)$으로 꽤 효율적이다.

단순한 방법이지만 단일 수에 대한 소수 여부 검사엔 적합하지 않다.

 

 

2. 약수의 성질 활용

약수가 대칭성을 갖는다는 사실을 활용하는 것이다.

어떤 수 $N$의 제곱근을 $\sqrt(N)$이라고 할 때, $\sqrt(N)$의 약수로 소수 여부를 판단할 수 있다.

코드로 옮기면 다음과 같다.

 

function isPrime(n) {
    if (n <= 1) return false;
    if (n === 2) return true;
    if (n % 2 === 0) return false;

    const sqrt = Math.sqrt(n);
    for (let i = 3; i <= sqrt; i += 2)
        if (n % i === 0) return false;

    return true;
}

시간 복잡도가 $O\sqrt{N}$이기 때문에 체를 사용하는 것보다 효율적이다.

하지만 약수의 성질도 활용하면서 소수의 성질을 적극 활용할 수 있는 방법이 또 있다.

 

 

3. 쌍둥이 소수

쌍둥이 소수란 간단히 말해서 2와 3을 제외한 모든 소수는 6k ± 1의 형태를 띠고 있다는 것이다.

쌍둥이 소수 - 위키백과, 우리 모두의 백과사전

 

단일 소수 판별에 있어선 가장 많이 사용된다고 해도 과언이 아닐 것이다.

코드로 옮기면 다음과 같다.

 

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;

    const sqrt = Math.sqrt(n);
    for (let i = 5; i <= sqrt; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }

    return true;
}

큰 흐름은 공유하고 있지만 더 효율적으로 동작한다.

1. 작은 수(2와 3)에 대한 신속한 확인
2. 약수의 성질을 활용해 검사 개수 감소
3. $6k ± 1$를 활용해 검사 개수가 $\frac{N}{3}$개로 감소

 

 

2. 조합

소수 판별 구현은 완료됐다.

이제 배열에서 조합을 뽑아야 한다.

3개로 할 수 있는 모든 조합을 찾아야 하기 때문에,

필연적으로 $O(N^3)$의 시간 복잡도를 가질 것 같다.

하지만 다음의 코드에선 불필요한 케이스들을 제거하므로 $O(N^2)$의 복잡도를 갖는다.

 

function countPrime(arr, choose, start = 0, sum = 0, count = 0) {
    if (choose === 0) {
        return isPrime(sum) ? 1 : 0;
    }

    let primeCount = 0;

    for (let i = start; i <= arr.length - choose; i++) {
        primeCount += countPrime(arr, choose - 1, i + 1, sum + arr[i], count + 1);
    }

    return primeCount;
}

3중 for문을 사용하면 중복된 조합을 생성할 수도 있기 때문에,

메모이제이션 등으로 최적화를 해야 한다.

하지만 위 코드는 필요한 조합만 생성하므로 보다 효율적으로 동작하게 된다.

 

 

3. 완성

완성된 코드는 다음과 같다.

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;

    const sqrt = Math.sqrt(n);
    for (let i = 5; i <= sqrt; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }

    return true;
}

function countPrime(arr, choose, start = 0, sum = 0, count = 0) {
    if (choose === 0) {
        return isPrime(sum) ? 1 : 0;
    }

    let primeCount = 0;

    for (let i = start; i <= arr.length - choose; i++) {
        primeCount += countPrime(arr, choose - 1, i + 1, sum + arr[i], count + 1);
    }

    return primeCount;
}

function solution(nums) {
    return countPrime(nums, 3);
}

소수 판별을 효율적으로 할 수 있는지가 중요한 문제였다고 생각된다.