에라토스테네스의 체

소수를 판별하는 알고리즘

소수란?

1과 자신 이외의 자연수로 나눌 수 없는 자연수

에라토스테네스의 체란?

수학에서 소수를 찾는 빠르고 쉬운 방법

알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다
3. 자기자신을 제외한 2의 배수를 모두 지운다
4. 남아있는 수 중 3은 소수이므로 오른쪽에 3을 쓴다
5. 자기자신을 제외한 3의 배수를 모두 지운다 (초록색)
6. 남아있는 수 중 5는 소수이므로 오른쪽에 5를 쓴다
7. 자기자신을 제외한 5의 배수를 모두 지운다 (파란색)
8. 남아있는 수 중 7는 소수이므로 오른쪽에 5를 쓴다
9. 자기자신을 제외한 7의 배수를 모두 지운다 (노란색)
10. 남는 수가 소수 (보라색)

=> 즉, 2의 배수, 3의 배수, 5의 배수, 7의 배수를 모두 지우고 남은 수가 모두 소수 (2,3,5,7 자기 자신은 소수)

알고리즘 풀이 그림

javascript로 구현

funtion solution(n){
  /** n만큼 배열을 만들고 초기값을 true로 지정
   * 배열은 0부터 시작하기 때문에 n + 1을 해줌
   * 0과 1은 소수이기때문에 초기에 false로 지정
   */
  const arr = Array(n + 1).fill(true).fill(false, 0, 2)

  // 2부터 시작하여 배열 총길이의 제곱근까지 반복
  for(let i =0;i * i <= n; i++){
    if(arr[i]){
      /** 소수가 아닌 수를 찾기
       * i*i는 배수
       * 예) i가 2일 경우 i*i = 4, j는 4부터 시작
       */
      for(let j = i * i; j <=n ;j+=i){
        arr[j] = false
      }
    }
  }
}

● 주석이 없는 코드

funtion solution(n){
  const arr = Array(n + 1).fill(true).fill(false, 0,2 )

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

● 에라토스테네스의 체 활용

const result = solution(10);

// 소수 개수 찾기
result.filter((n) => n).length;

// 소수 찾기
const arr = [];
result.forEach((n, i) => {
  if (n) {
    arr.push(i);
  }
});

// 소수 찾기 2
result.map((v, i) => (v ? i : 0)).filter((e) => e);

참고 블로그

• [위키백과] 에라토스테네스의 체
• [알고리즘] 소수 찾기 - 에라토스테네스의 체 by javascript