[JavaScript] 에라토스테네스의 체 진짜 쉽게 설명해줌 (소수 찾기)

[JavaScript] 에라토스테네스의 체 진짜 쉽게 설명해줌 (소수 찾기)

에라토스테네스의 체란?

• 소수를 찾는 방법 중 하나
• 불필요한 반복을 줄이고 알고리즘의 효율성을 높이는 방법
• 소수 찾을 때 에라토스테네스 체 쓰세요

---

에라토스테네스의 개념

일단 자연수 n까지의 소수를 에라토스테네스의 체를 통해 찾는다고 하면 다음과 같은 과정을 거칩니다.

1. 2부터 n까지의 모든 정수를 나열
2. 가장 작은 소수인 2를 찾아 2의 배수를 모두 지움
3. 아직 지우지 않은 가장 작은 소수인 3을 찾음 (3도 소수). 3의 배수를 모두 지움
4. 위 과정을 n의 제곱근까지 반복 (n보다 큰 소수의 배수는 이미 작은 소수의 배수에 의해 제거되었기 때문)
5. 지우지 않고 남아있는 수들이 곧 2부터 n까지의 모든 소수

 

예시를 보여주자면,

2부터 10까지 소수를 판별하기 위해 에라토스테네스의 체를 적용해 보겠습니다

1. 2부터 10까지의 숫자를 나열

2  3  4  5  6  7  8  9  10

1. 첫 번째 소수인 2를 찾아 2의 배수를 모두 지움 (2는 안지움)

2  3     5     7     9

1. 다음 소수인 3을 찾아 3의 배수를 모두 지움 (3은 안지움)

2  3     5     7

1. 다음 숫자인 5는 소수임. 하지만 10보다 큰 5의 배수는 존재하지 않으므로 지울 게 없음
2. 7도 소수임. 하지만 10보다 큰 7의 배수 없으므로 지울 게 없음
3. 이제 더 이상 지울 게 없으므로 종료

따라서, 2부터 10까지의 소수는 2,3,5,7입니다.

---

에라토스테네스의 체 코드에 적용하기

자연수 n 이하의 모든 소수를 판별하는 코드를 작성해보겠습니다.

function findPrimes(n) {
  let primes = Array(n + 1).fill(true).fill(false, 0, 2);

  for (let i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes.filter((e) => e).length;
}

• 함수 findPrimes는 자연수 n을 받아 2부터 n 이하의 소수를 찾아 개수를 return하는 함수

let primes = Array(n + 1).fill(true).fill(false, 0, 2);

• 를 통해 길이가 n+1인 배열을 생성하고 모든 값을 true로 채워줌
• 0과 1은 소수가 아니므로 false로 설정
• fill의 중복 사용에 대해 헷갈린다면, 아래 링크를 참고하세요
• https://developer-haru.tistory.com/31

 

• 처음의 for 루프에서는 에라토스테네스의 체 알고리즘을 적용
• 인덱스 i가 소수라면, 그 배수는 소수가 아님을 나타내기 위해 false로 설정
• 이를 위해 j = i * i 에서 시작해 j를 i만큼 증가시키며 반복
• 마지막 for 루프에서 isPrime 배열에 filter를 적용해 true로 설정된 값들의 길이를 구함

---

왜 에라토스테네스가 효율적인가 ?

• 그냥 냅다 for문 돌리고 싶은데, 왜 이렇게 굳이 복잡한 로직을 사용해야 하는가?
• 에 대한 정답은 효율성에 있습니다
• 반복문이 시작할 때 i는 2부터 시작하고, j는 i*i 부터 시작합니다
• i가 2일때, j는 2의 배수인 4, 6, 8을 지우고 i가 3이 되면 j는 3의 배수인 9부터 지우게 됩니다
• 이 경우 i가 3이 되었을 때 j를 6부터 시작하게 하면 6은 이미 i가 2일때 지워진 상태입니다
• 즉, j를 i*i 부터 시작하게 하여 이미 지워진 숫자를 다시 확인하는 불필요한 작업을 줄이게 됩니다
• 이는 알고리즘의 효율성을 높히며, 이 과정을 통해 에라토스테네스의 체는 시간 복잡도가 O(n log log n)이라는 매우 효율적인 시간 복잡도를 가지게 됩니다