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

소수 판별 문제를 풀다가 시간초과에 걸려 방법을 찾아보던 중 에라토스테네스의 체 라는 알고리즘을 알게 되었습니다

 

자연수의 분류

 

- 1은 소수도 합성수도 아님

- 소수는 1과 자기자신만을 약수로 가지는 수 = 약수가 2개인 수

- 합성수는 1을 제외하고 소수가 아닌 수

 

 

✓ 기본적인 소수 찾기

2부터 √n까지 확인했을 때 n % i === 0 인 수가 하나라도 있으면 n은 합성수

→ n은 √n 이하의 약수를 가지면 합성수

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

 

 

n = 36 일 때 n의 약수를 i * i <= n 까지만 확인해도 되는 이유는

n이 합성수라면 n = a x b의 형태에서 a 또는 b 중 하나가 반드시 √n 이하에 존재하기 때문

 

 

 

위 방법은 하나의 수에 대해서 소수인지 확인할 때는 빠른 방법이지만,

n까지의 수 중에서 모든 소수를 구하는 문제에서는 에라토스테네스의 체를 사용하여 훨씬 효율적으로 해결할 수 있습니다

 

 

✓ 에라토스테네스의 체 소수 찾기

0~n만큼 true 값으로 배열을 생성하고 2부터 √n까지의 수를 기준으로 그 배수들을 false로 바꾸며 최종 true인 값이 소수

  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;
    }
  }

 

 

예시로 n = 20 경우에는 다음 순서대로 제거하며 소수가 남게 됩니다