소수 찾기, 에라토스테네스의 체 (프로그래머스)


=> 에라토스테네스의 체는 고대 그리스 수학자가 발견한 알고리즘으로 제곱근의 배수를 지우면 소수만 남는 알고리즘이다.

function solution(n) {
 const dimension = [false, false, ...Array(n - 1).fill(true)]
 for (let i = 2; i * i < n; i++) {
    if (dimension[i]) {
        for (let j = i * 2; j <= n; j += i) {
            dimension[j] = false

        }
    }
 }
 return dimension.filter(Boolean).length
}

좋은 웹페이지 즐겨찾기