에라토스테네스의 체를 이용해서 소수인지 판별하기

구현

const eratostenes = (number) => {
        if (number <= 1) {
            return false
        }
        for (let num = 2; num <= number ** 0.5; num++) {
            if (number % num === 0) {
                return false
            }
        }
        return true
    }

console.log(eratostenes(11)) // true
console.log(eratostenes(24971)) // true
console.log(eratostenes(249713)) // false

시간복잡도

• O(logN)

특징

• 제곱근을 한 숫자까지 탐색하여 소수를 판별
• 기존의 number 전체를 탐색하는 것이 아니기 때문에 시간복잡도가 O(N)에서 O(logN)으로 줄어든다.