에라토스테네스의 체는 2부터 수를 순회하며 현재 숫자의 해당하는 모든 배수를 제거해가며 소수를 찾아내는 방식이다. 아래 첨부파일에서는 120보다 작은 소수를 구하는 것이기에 11까지만 해도 소수를 구하기에 충분하다. 왜냐하면 11의 제곱은 121이기 때문에 11 이후의 숫자부터는 11보다 작은 수와 합성수로 120이 되었을 것이고, 그 이외의 수들은 120의 약수가 되기 어렵기 때문이다.
이 알고리즘을 자바스크립트로 구현해보면 !
function solution(n) {
var answer = new Array(n + 1).fill(true)
let max = Math.pow(n, 0.5)
for (let i = 2; i < max + 1; i++) {
if (answer[i]) {
for (let j = i * 2; j <= n; j += i) {
answer[j] = false
}
}
}
return answer.slice(2).filter(ele => ele && ele).length;
}배열의 인덱스는 0번부터 시작하므로 순회하는 숫자와 인덱스가 일치하는 곳에 true/false 값을 넣고 싶어서 주어진 숫자에 1을 더한 배열을 만들었다. 첫 값은 다 true으로 주었고, 배열을 순회하면서(0, 1번 째 인덱스 값은 소수가 아니므로 2부터 시작) 값이 true면 해당 숫자의 배수들을 전부 false 처리했다. 그리고 true를 필터링하기 전에 0번째와 1번째 인덱스는 무시해야하므로 자르고 필터 함수를 썼다.
에라토스테네스의 체를 사용하면 시간 복잡도가 O(Nlog(logN))으로 O(N)에 가깝다고 한다.
얼레벌레 개발자