SMALL
소수 찾기 (시간복잡도 고려해서)
* 에라토스테네스의 체 :
// 에라토스테네스의 체
function solution(n) {
var answer = 0;
function eratostenes(m) {
// 0과 1은 소수에서 제외
let arr = new Array(m+1).fill(true).fill(false, 0, 2);
// i*i >>> 11^2가 120보다 큰 경우는 의미가 없다
for(let i=2 ; i*i <= m ; i++) {
if(arr[i]){
for(let j=i*i; j<=m; j+=i) {
arr[j] = false; // 배수 제거
}
}
}
return arr;
}
let isPrimes = eratostenes(n);
answer = isPrimes.filter(e => e).length;
return answer;
}
728x90
'Algorithm > Javascript' 카테고리의 다른 글
[프로그래머스] 230921 코딩테스트 연습 (0) | 2023.09.21 |
---|---|
[프로그래머스] 230920 코딩테스트 연습 (0) | 2023.09.20 |
[프로그래머스] 230919 코딩테스트 연습 (0) | 2023.09.19 |
[프로그래머스] 230918 코딩테스트 연습 (0) | 2023.09.18 |
[프로그래머스] 230915 코딩테스트 연습 (0) | 2023.09.18 |
댓글