[알고리즘] 에라토스테네스의 체

jay__ss·2023년 4월 13일
0

알고리즘

2부터 타겟 숫자까지 모든 숫자를 나열한다.(10이라면 2, ... , 10)
순회를 시작하면서, 숫자가 소수라면 그의 배수들을 모두 지운다.
단, 지울 때 소수인 숫자는 내버려둔다.
그렇게되면 최초 2를 시작으로, 3, 5, 7 등의 배수들이 지워진다.

코드

// 타겟 숫자 n을 받으면
// n 까지 소수 갯수를 반환하는 함수
function isPrime(n) {
  // index는 0부터 시작하니 n + 1 까지 생성
  // arr는 해당숫자(인덱스)가 소수면 true, 아니면 false
  const arr = new Array(n + 1).fill(true);
  // 0, 1은 소수가 아니니 false 처리
  arr.splice(0, 2, false, false);

  // 2부터 순회를 시작하나, 제곱수부터는 순회를 하지 않음
  // 어떤수의 제곱이다 === 이미 소수가 아니다
  for(let i = 2; i ** 2 <= n; i += 1) {
      // 만약 해당숫자가 소수라면, 그 숫자의 배수들을 제거할것임
      if (arr[i]) {
          // 제곱수부터 해당숫자만큼 더해줄것임
          for(let j = i ** 2; j <= n; j += i) {
              arr[j] = false;
          }
      }
  }

  // console.table(arr);
  return arr.filter(el => el).length;
}
profile
😂그냥 직진하는 (예비)개발자

0개의 댓글