JavaScript_에라토스테네스의 체

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

• 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
  자기 자신을 제외한 2의 배수를 모두 지운다.
• 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
  자기 자신을 제외한 3의 배수를 모두 지운다.
• 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
  자기 자신을 제외한 5의 배수를 모두 지운다.
• 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
  자기 자신을 제외한 7의 배수를 모두 지운다.

"위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다."

그림의 경우, {\displaystyle 11^{2}>120}{\displaystyle 11^{2}>120}이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

코드로 구현

JavaScript 로 구현

function solution(n) {
  var answer = 0;
  const ch = Array.from({ length: n + 1 }, () => true);
  ch[0] = false;
  ch[1] = false;
  for (let x = 2; x < Math.sqrt(n) + 1; x++) {
    if (ch[x] === true) {
      for (let j = x + x; j < n + 1; j += x) {
        // 배수 만큼 for문 증가
        ch[j] = 0;
      }
    }
  }
  answer = ch.reduce((acc, cur) => acc + cur);
  return answer;
}

Python 으로 구현

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]