[Programmers] level 1: 소수 찾기 by JavaScript

 이번 글을 작성하는 데 아래 포스팅들을 참고하였습니다.

 

• 개발꿈나무 님의 포스팅

JavaScript__에라토스테네스의 체 구현 - 개발꿈나무의 개발로그

• 기록의 힘 님의 포스팅

[JavaScript] 자바스크립트 소수 판별하기(feat. 반복문, 에라토스네테스의 체)

---

이번 문제를 풀어 보고 싶다면? 아래 링크를 클릭하세요!

☞ 문제 풀러 가기!

 

 처음에 이중 for문을 통해 풀려고 하니까 시간 초과가 떴다. 어떻게 하면 실행 시간을 줄일 수 있을지 구글링을 해보니 탐색 범위를 주어진 수의 제곱근까지로만 설정하면 된다고 했다. 

 내가 작성한 해답의 경우 주어진 수가 2라면 바로 1을 반환하고, 아니라면 for 반복문으로 탐색을 시작하는데 primeChecker라는 함수를 통해 소수를 찾아낸다. i가 2로 나눠진다면(짝수라면) 즉시 false를 반환하고 아니라면 3부터 제곱근까지 for문을 돌려 i보다 작은 수 중 나눠떨어지는 값이 있는지 찾는다. 어떠한 조건에도 해당하지 않는다면 소수 이므로 true를 반환한다.

 두 번째로 찾은 해답이 바로 소수를 찾을 때 흔히 쓰이는 '에라토스테네스의 체'이다. 특정 값이 소수인지 판별하기보다 일정 범위 내의 숫자 중 소수를 찾아내는 데 유용하다. 아래 그림과 같이 주어진 숫자 범위 내에서 가장 작은 소수를 찾고 그 소수 자기 자신을 제외한 해당 소수의 모든 배수들을 제거하기를 반복한다. 반환값은 filter() 메서드를 활용하여 true인 요소의 개수를 반환하도록 했다.

에라토스테네스의 체.gif

 

Solutions

function solution(n) {
  /* My Solution */
  if (n === 2) return 1
  let answer = 1;
  for (let i = 3; i <= n; i++) {
      const isPrime = primeChecker(i)
      if (isPrime) answer++
  }
  return answer;

  /* Eratosthenes' Sieve*/
  let answer = Array(n + 1)
    .fill(true)
    .fill(false, 0, 2);
  // Array()에서 괄호 안의 숫자는 인덱스이므로 주어진 수까지 채우려면 n + 1 해줘야 함.
  // 0과 1은 소수가 아니므로 false 처리

  for (let i = 2; i <= Math.floor(Math.sqrt(n)); i++)
    if (answer[i]) for (let j = i * i; j <= n; j += i) answer[j] = false;

  return answer.filter((val) => val === true).length;
}

function primeChecker(i) {
  if (i % 2 === 0) return false;
  for (let j = 3; j <= Math.floor(Math.sqrt(i)); j++)
    if (i % j === 0) return false;
  return true;
}