소수의 개수 파악 - 에라토스테네스의 체

 

  에라토스테네스의 체는 특정 수가 주어졌을 때 2부터 특정 수까지의 범위 중 소수의 개수를 파악하는 방법이다. 알고리즘의 순서는 아래와 같다.

 

1. 2 부터 구하고자 하는 구간의 모든 수를 나열한다.
2. 첫번째 수인 2 자기 자신을 제외하고 자신의 배수를 모두 지운다.
3. 남은 수들 중 다음수에 대하여 단계 2를 반복한다.

 

 

이를 자바스크립트 코드로 구현하면 아래와 같다.

 

function solution(n) {
	// 1. 2부터 n까지의 모든수를 배열에 저장
    let arr = new Array(n - 1).fill(2).map((ele, idx) => ele += idx); 

    for (let i = 0; i < arr.length; i++) { // 2. 모든 수에 대해 순회                           
        // 3. 인덱스의 수가 0일 경우(지워진 수일 경우) 다음 인덱스로 넘김
        if (arr[i] === 0) continue;                                   
        
        // 4. 해당 인덱스의 배수를 모두 제거
        for (let j = i + arr[i]; j <= n; j += arr[i]) {               
            arr[j] = 0;
        }
    }
    
    return arr.filter(ele => ele)  // 5. 제거된 수(0) 필터링                                   
 }
 
 console.log(solution(90))                                            
 // [2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89]