[프로그래머스 JavaScript] 소수 찾기

프로그래머스 Level1 소수찾기

 

문제 설명 : 생략

 

function solution(n) {
  //효율성 통과를 위해 에라토스테네스의 체 이용
  var answer = 0;
  let num = new Array(n + 1);

  //인덱스에 해당 값 세팅
  for (let i = 2; i <= n; i++) {
    num[i] = i;
  }

  //각 인덱스의 배수값은 소수가 아니므로 0으로 세팅
  for (let j = 2; j <= n; j++) {
    if (num[j] === 0) continue;

    for (let k = j * 2; k <= n; k += j) {
      num[k] = 0;
    }
  }

  //0이 아닌 것들은 소수이므로 탐색
  for (let i = 2; i <= n; i++) {
    if (num[i] !== 0) answer += 1;
  }

  return answer;
}

코드 설명 : 소수를 구하는 여러가지 방법이 있다. 저는 보통 약수를 이용한 제곱근 소수 알고리즘을 사용합니다.

하지만 이 문제는 n을 소수판별이 아닌 n까지 소수의 개수를 구하는 알고리즘 이므로 다른 방식을 사용한다.

여러 방식도 있지만 이 문제에서는 효율성 테스트도 있기 때문에 비교적 시간복잡도가 제일 낮은 "에라토스테네스의 체" 방식의 알고리즘을 사용한다.

"에라토스테네스의 체" 방식을 간략하게 설명하자면 각 수의 배수에 해당하는 수는 소수가 아니므로 지운다.

ex)3,6,9가 있다면 6,9는 3의 배수가 아니므로 지워도 무방하다.

이런식으로 지워나간 후, 남아있는 수를 파악하면 그것이 소수의 개수가 된다.