[JS] 프로그래머스 - 소수 찾기 (에라토스테네스의 체 알고리즘)

📌  문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

✏️  풀이

📣  에라토스테네스의 체

✔️ 소수를 판별하는 알고리즘 (대량으로 빠르고 정확하게)

✔️ 소수를 판별할 수만큼 배열을 할당하고, 하나씩 지워가는 방법

     ➰ 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.

     ➰ 지울 때, 자기 자신은 지우지 않고 이미 지워진 수는 건너뛴다.

     ➰ 2부터 시작해서 남아 있는 수를 출력한다.

 

📣  에라토스테네스의 체 구현 코드

function prime(n) {
  let answer = 0;
  let arr = [];
  
  for(let i=2; i<=n; i++){  // 배열 초기화 하기
    arr[i] = i
  }

  for(let i=2; i<=n; i++){  // 2부터 돌면서 
    if(arr[i] === 0){ // 이미 지워진 수라면 건너뛰고
      continue;
    }
    else{
      for(let j= 2*i; j<=n; j+=i){  // 안지워진 수라면 그 수의 배수부터 시작해서 모든 배수 지우기
        arr[j] = 0;
      }
    }
  }

  for(let i=2; i<=n; i++){
    if(arr[i] !== 0){
      answer++;
    }
  }

  return answer;
}