Sieve of Eratosthenes(에라토스테네스의 채)

들어가기에 앞서, 중1 때 배웠던 소수와 합성수에 대해서 잠깐 알아보면 더 이해가 잘 될 것이다.

 

소수와 합성수

---

 

1보다 큰 모든 정수는 소수이거나 합성수이다.

 

• 소수는 1과 자기 자신으로 밖에 나누어 떨어지지 않는 수이다. (두 개의 약수만 가지고 있다.)
• 합성수는 1과 자기 자신이 아닌 다른 자연수의 곱으로 나타낼 수 있는 자연수를 의미한다. (두개 이상의 약수를 가지고 있다.)
• 따라서 1은 소수도 합성수도 아니다.

 

Sieve of Eratosthenes(에라토스테네스의 채)

---

 

간단하게 말하면, 1부터 어떤 수 N까지의 범위에서 소수들을 찾는 방법이다.
고대 그리스 수학자 에라토스테네스가 발견하였으며, 구하는 방법이 마치 채에 거르는 것과 같아 '에라토스테네스의 채'라고 불린다. 알고리즘은 아래의 이미지를 보고 이해하면 더 쉬울 것이다. 

 

예를 들어, 1부터 100까지 범위 중에서 소수를 구해보자.

 

에라토스테네스의 채

1. 1은 소수도 합성수도 아니라고 위에 설명했으니 지워준다. 보통 이 이론을 설명할 때 숫자들을 2부터 나열하는 이유이기도 하다.
2. 2부터 시작해서 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 3부터 시작해서 자기자신을 제외한 3의 배수를 모두 지운다.
4. 4는 이미 2단계에서 지워졌으므로 5로 넘어가서 5부터 시작해서 자기 자신을 제외한 5의 배수를 모두 지운다.
5. 6은 이미 2단계에서 지워졌으며로 7로 넘어가서 자기 자신을 제외한 7의 배수를 모두 지운다.
6. 2-5단계의 과정을 계속해서 반복하면 소수만이 지워지지 않고 남게 된다.

이를 javascript로 구현하면 아래 코드와 같다.

const sieve = max => {
  // 채로 사용할 배열을 만들어서 값을 true로 채워준다.
  const sieve = new Array(max+1).fill(true)

  // 2부터 시작해서 max의 제곱근까지만 구하면 된다.
  // 이유는 i * i의 값이 범위의 최대 수를 넘으면 계산할 필요가 없기 때문이다.
  for (let i = 2; i <= Math.sqrt(max); i++) {
    if (sieve[i]) {
      for (let j = Math.pow(i, 2); j <= max; j += i) { // i의 배수들을 false로 바꿔준다.
        sieve[j] = false
      }
    }
  }

  // 이제 sieve의 배열에서 값이 true인 index만 추리면 된다.
  return sieve.reduce((primes, isPrime, i) => {
    if (isPrime && i > 1) { //i가 0인 경우는 제외해야하기 때문에 i > 1 조건 추가
      primes.push(i)
    }
    return primes
  }, [])

}

sieve(23)을 돌려보면 [ 2, 3, 5, 7, 11, 13, 17, 19, 23 ]가 나오는 것을 알 수 있다.