[소수 판별] 에라토스테네스의 체 - JS

에라토스테네스의 체

소수 판단 알고리즘
소수들을 대량으로 빠르고 정확하게 구하는 방법

 

단일 숫자 소수 여부 확인

• 어떤 수의 소수 여부 확인할 때는 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N*1/2)의 시간 복잡도로 빠르게 구할 수 있음
• 수가 수(N)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N의 제곱근 이하이기 때문

원리

가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나감

• 배열을 생성하여 초기화
• 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. (지울 때 자기자신은 지우지 않고 이미 지워진 수는 건너뛴다)
• 2부터 시작하여 남아있는 수를 모두 출력한다

 

Array() : 배열 초기화

Array안에 수(n)를 넣으면 n만큼 인자 넣을 자리가 생김
fill을이용하여 넣어주기

Array(11).fill(true).fill(false, 0, 2) //[ false, false, true, true,  true,  true, true,  true,  true, true,  true]

 

fill

배열을 같은 값으로 채움
arr.fill(value, ?start, ?end)

let arr = [a, b, c, d]

arr.fill('A', 1, 3)
console.log(arr) // [a, A, A, d]

 

소수 개수 구하기

function solution(n) {
    let arr = Array(n+1).fill(true).fill(false, 0, 2)
    //i의 제곱이 n보다 작을 때 까지 
    for (let i = 2; i*i <= n; i ++) {
        if(arr[i]) {
            //j는 i의 제곱
            //j(i*i)가 n보다 작을 때까지
            //j+i씩 증가 
			//i가 2일경우 4, 6, 8, 10 ... 100
			//i가 3일경우 9, 12, 15, 18 ... 99
            for (let j=i*i; j<=n; j+=i) {
                arr[j] = false
            }
        }
    }
    
    return arr.filter(e => e).length;
}

solution(100)