[JS] 소수 만들기

function solution(nums) {
    let answer = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                let sum = nums[i] + nums[j] + nums[k];
                if(isPrime(sum)) answer++;
            }
        }
    }
    return answer;
}
const isPrime = (sum) => {
        for(let i = 2; i < sum; i++) {
            if(sum % i === 0) return false;
    } return true;
}

 

 

isPrime 함수는 주어진 수 sum이 소수인지 아닌지를 판단합니다.

소수(prime number)는 1과 자기 자신 외에 아무로 나누어 떨어지지 않는 수를 말합니다.

함수는 2부터 sum - 1까지의 숫자들로 나누어 나머지가 0이 되는 경우가 있는지 확인합니다.

만약 나누어 떨어지는 경우가 있으면 소수가 아니므로 false를 반환하고, 모든 경우를 검사한 후에도 나누어 떨어지는 경우가 없다면 true를 반환하여 소수임을 나타냅니다.

 

 

 

다른 사람 풀이

function solution(nums) {
    let answer = 0;
    
    for (let i = 0; i<nums.length-2; i++) {
        for (let j = i+1; j<nums.length-1; j++) {
            for (let k = j+1; k<nums.length; k++) {
                let sum = nums[i] + nums[j] + nums[k]
                answer++;
                
                for (let n = 2; n<=Math.sqrt(sum); n++) {
                    if (sum % n === 0) {
                        answer--;
                        break;
                    }
                }
            }
        }
    }
    
    return answer;
}

 

소수의 정의와 나누어 떨어지는 수의 성질

소수(prime number)는 1과 자기 자신 외에 다른 숫자로 나누어 떨어지지 않는 수입니다. 예를 들어, 29는 소수입니다. 29의 제곱근을 보면, √29 ≈ 5.39입니다. 따라서 29를 나누어 떨어지는 수는 2, 3, 4, 5 중 하나여야 합니다. 만약 29가 2, 3, 4, 5로 나누어 떨어지지 않으면, 29는 소수입니다.

 

 

제곱근을 사용하는 이유 ( 효율성 향상 )

위의 성질을 이용하면, 수 n이 소수인지 확인하기 위해 2부터 √n까지의 숫자로만 나누어보면 충분합니다. 만약 이 범위 내에서 나누어지는 수가 없다면, 나머지 수로 나누어 떨어지지 않는다는 것을 보장할 수 있습니다.

이렇게 하면 반복 횟수를 크게 줄일 수 있으므로, 소수 판별 알고리즘이 더 효율적으로 동작합니다.