에라토스테네스의 체

정의

그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

 

아이디어

1. 0-n까지 들어있는 배열을 만든다. 여기서 소수가 아닌 숫자는 모두 0이 될 것이다.

2. 1을 0으로 만든다. (1은 소수가 아니므로 처리한다.)

3. 반복문을 돌리면서 만약 해당 숫자가 살아 있다면, 그 숫자는 소수이다. 그리고 그 숫자의 n배는 소수가 아니므로 0으로 바꾼다.

4. 마지막에 filter를 이용하여 0을 제거하면 소수만 모여있는 배열이 남는다.

 

구현

function solution(n){
	// 1. 초기 배열 선언
    let arr = Array(n+1).fill().map((_,i) => i).fill(0,1,2)
    
    // 2. 체 작업
    for(let i = 2 ; i * i <= n; i++){
        if(arr[i]){
            for(let j = i * i; j <= n; j+=i){
                arr[j] = 0;
            }
        }
    }
    return arr.filter(x=> x)
}

1. 초기 배열을 선언한다.

  - .fill()을 이용해 n+1개의 undefined를 채운다. ex). [undefined, undefined, undefined,]

  - .map()을 이용해 0부터 n으로 바꾼다. ex). [0, 1, 2]

  - .fill로 1번째항을 0으로 한다. [0,0, 2] (1은 소수가 아니므로 미리 0으로 만든다.)

 

2. 체 작업을 진행한다.

 - n까지의 소수를 알고 싶다면 n의 제곱근까지만 구하면된다. 왜냐면 어떤 약수든 n의 제곱근보다 하나는 작기 때문이다.

 

3. 마지막에 filter를 이용하여 0을 제거한다. filter는 false값을 모두 제거한다.

 

 

 

참고

 [네이버 지식백과] 에라토스테네스의 체 [Eratosthenes' sieve] (두산백과 두피디아, 두산백과)

- mdn, fill : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/fill

- mdn, filter : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/filter