[프로그래머스/Javascript] Lv.1 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

 

✓ 풀이과정

 

처음 시도 했던 과정은 아래와 같습니다

 

1. 2부터 제곱근까지 확인하며 나누어 떨어지는 수가 없으면 소수라고 판별하여 카운트 추가

2. 2부터 n까지 돌면서 1번 반복하며 최종 소수 카운트 반환 

 

function solution(n) {
  let answer = 0;

  const isPrime = (num) => {
    for (let i = 2; i * i <= num; i++) {
      if (num % i === 0) return false;
    }
    return true;
  };

  for (let i = 2; i <= n; i++) {
    if (isPrime(i)) answer++;
  }

  return answer;
}

 

위 방법으로 시도했을 경우 일부 항목에서 시간초과가 발생하여 더 효율적으로 소수를 찾을 수 있는 방법을 찾아보다

에라토스테네스의 체 알고리즘을 발견하게 되어 해당 알고리즘을 적용하여 코드를 수정하였습니다

 

 

참고. [개발/코딩테스트] - [코딩테스트] 소수 찾기와 에라토스테네스의 체

[코딩테스트] 소수 찾기와 에라토스테네스의 체

 

 

✓ 최종코드

function solution(n) {
  let isPrime = Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let i = 2; i * i <= n; i++) {
    if (!isPrime[i]) continue;

    for (let j = i * i; j <= n; j += i) {
      if (!isPrime[j]) continue;
      isPrime[j] = false;
    }
  }

  return isPrime.filter((v) => v).length;
}