[프로그래머스] 소수 만들기 - js

이번에 푼 문제는 프로그래머스의 소수 만들기 문제이다.
코딩테스트 연습 - 소수 만들기

---

문제

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
  
  

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 #1

1. [1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2

1. [1,2,4]를 이용해서 7을 만들 수 있습니다.
2. [1,4,6]을 이용해서 11을 만들 수 있습니다.
3. [2,4,7]을 이용해서 13을 만들 수 있습니다.
4. [4,6,7]을 이용해서 17을 만들 수 있습니다.

---

풀이

1. 에라토스테네스 체를 이용한 소수 배열 만들기:
   n은 최대 1000이며 3개의 숫자를 더해주므로 3001크기의 배열을 만들어준다. 그리고 에라토스테네스 체를 이용해 3000까지의 수 중에서 소수인 수를 판별하는 numArr 배열을 구한다.

2. 3중 for문을 이용해 가능한 모든 조합들이 소수인지 판별하기:
   sum = nums[i] + nums[j] + nums[k]로 배열의 서로다른 3개의 원소를 더한 후, 해당 sum이 소수일 시 answer을 1 더해준다.

---

전체 코드

// 가능한 모든 조합이 소수인지 판별하는 과정
function solution(nums) {
    let answer = 0;
    let arrLen = nums.length;
    const primeArr = makePrime();
    
    for (let i = 0; i < arrLen - 2; i++) {
        for (let j = i+1; j < arrLen - 1; j++) {
            for (let k = j+1; k < arrLen; k++) {
                let sum = nums[i] + nums[j] + nums[k];
                (primeArr[sum]) && answer++;
            }
        }
    }
    return answer;
}

// 에라토스테네스 체를 이용해 3000까지의 수 중 소수인 수를 판별
function makePrime () {
    const numArr = new Array(3001).fill(true);
    for (let i = 2; i**2 <= 3000; i++) {
        if (!numArr[i]) continue;
        for (let j = i**2; j <= 3000; j+= i) {
            numArr[j] = false;
        }
    }
    return numArr;
}