[JS] Summer/Winter Coding(~2018) > 소수 만들기

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

let sieve = new Array(2997).fill(true);

for (let i = 2; i * i < sieve.length; i += 1) {
  if (!sieve[i]) continue;
  for (let j = i + i; j < sieve.length; j += i) {
    sieve[j] = false;
  }
}

console.log(sieve);
function solution(nums) {
  var 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++) {
        const index = nums[i] + nums[j] + nums[k];
        if (sieve[index]) {
          answer += 1;
        }
      }
    }
  }

  return answer;
}

이번 문제는 혼자 풀지 못 하고 다른 사람 풀이를 참고했다.

소수를 구하기 위해 '에라토스테네스의 체'라는 알고리즘을 사용해야 하는데 코드를 보고 풀어보려해도 풀리지 않았기 때문에..

알고리즘을 공부한 후 다시 문제를 풀어봤다.

에라토스테네스의 체 알고리즘은 주어진 배열만큼 모두 소수를 뜻하는 'true'로 변경한 후,

해당 인덱스의 값이 2,3,5,... 등의 배수일 경우 값을 false로 변경해준다.

그 후에 true의 개수를 구하면 소수의 개수가 몇 개인지 알 수가 있다!

 

위의 코드에서 배열의 길이를 2997로 준 것은 3개의 숫자가 1~1000까지의 숫자이지만 세 숫자는 중복되지 않기 때문에 최대값인 2997로 설정을 했다.

false 즉 소수가 아닌 경우는 for 반복을 타지 않고 true(소수)인 경우에만 반복을 타면서 i의 배수를 모두 false로 만들어 준다.

그렇게 소수인 숫자만 true로 변경한 후에 그 숫자를 계산하면 된다.