[TIL 2주차 - 230621] - 에라토스테네스의 체

1.문제

프로그래머스의 소수 찾기 문제를 풀어봤다.
이전에 소수 찾는 문제를 풀땐 시간을 고려하지 않고 풀었었다.
하지만 이번 문제는 정확성 뿐만 아니라 실행시간도 고려를 해야 했다.

2.시도 및 해결

• 내 첫 번째 코드 :

function solution(n) {
    let arr = [];
function isPrime(num) {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
}

for (let i = 2; i <= n; i++) {
  if (isPrime(i)) {
    arr.push(i);
  }
}
    return arr.length;
}

이렇게 푸니 효율성 테스트에서 실패 했다. 어떤 정수의 제곱근을 기준으로 나열된 약수들은 서로 대칭이므로 제곱근 이하로만 반복문을 실행하면 되기 때문에 위의 코드를 작성하기로 했었다. 하지만 문제는 아래의 for 반복문이 n번 반복 실행해야 하기 때문에 시간초과가 발생하는 것.

이를 위해 '에라토스테네스의 체' 라는 소수 찾기 알고리즘을 공부했다.
에라토스테네스의 체는 2,3,5,7을 제외하고 이 숫자들의 배수를 전부 지우는 방식이다.

만약 입력값이 14라고 가정했을 때,
2를 제외한 2의 배수는 4,6,8,10,12,14 가 있다. 이 숫자들을 전부 제거하는 방식이다.
3을 제외한 3의 배수는 9,12 가 있다. 이때, 12를 지우려고 하는데 이미 12가 지워졌으므로 건너 뛰어도 된다. 그러면 기존 로직에 비해 반복문의 실행 횟수가 줄어들것이다.

에라토스테네스의 체를 사용할 때도 반복문은 제곱근 이하 까지만 실행하면 된다.

function solution(n) {
    let arr = new Array(n + 1).fill(true);
    arr[0] = false;
    arr[1] = false;
    for (let i = 2; i * i <= n; i++) {
      if (arr[i]) {
        for (let j = i * i; j <= n; j += i) {
          arr[j] = false;
        }
      }
    }
    
    return arr.filter((a) => a).length;
}

3.배운 것.

• 정수의 제곱근을 기준으로 약수가 대칭이란 것.
• 에라토스테네스의 체를 코드로 구현해본 것.