[프로그래머스/자바스크립트(JavaScript)] 소수 찾기 (feat. 에라토스테네스의 체)
글 작성자: 망고좋아
반응형
🎯 소수 찾기
📁 문제 출처
💡 생각
- 소수는 에라토스테네스의 체로 구해놓고 풀면 시간 복잡도를 줄일 수 있다.
자바스크립트 에라토스테네스의 체
function prime() {
let n = 1000000;
let arr = Array(n + 1).fill(true).fill(false, 0, 2);
for (let i = 2; i < Number(n ** 0.5) + 1; i++) {
if (arr[i]) {
for (let j = i * i; j <= n; j += i) {
arr[j] = false;
}
}
}
return arr;
}
🛠 나의 코드
function prime() {
let n = 1000000;
let arr = Array(n + 1).fill(true).fill(false, 0, 2);
for (let i = 2; i < Number(n ** 0.5) + 1; i++) {
if (arr[i]) {
for (let j = i * i; j <= n; j += i) {
arr[j] = false;
}
}
}
return arr;
}
function solution(n) {
let ans = 0;
let arr = prime();
for(let i = 1; i <= n; i ++ ) {
if (arr[i] === true) {
ans += 1
}
}
return ans;
}
반응형
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/자바스크립트(JavaScript)] 문자열 내림차순으로 배치하기 (0) | 2021.09.17 |
---|---|
[프로그래머스/자바스크립트(JavaScript)] 문자열 다루기 기본 (0) | 2021.09.17 |
[프로그래머스/자바스크립트(JavaScript)] 수박수박수박수박수박수? (0) | 2021.09.17 |
[프로그래머스/자바스크립트(JavaScript)] 시저 암호 (0) | 2021.09.17 |
[프로그래머스/자바스크립트(JavaScript)] 이상한 문자 만들기 (0) | 2021.09.17 |
댓글
이 글 공유하기
다른 글
-
[프로그래머스/자바스크립트(JavaScript)] 문자열 내림차순으로 배치하기
[프로그래머스/자바스크립트(JavaScript)] 문자열 내림차순으로 배치하기
2021.09.17 -
[프로그래머스/자바스크립트(JavaScript)] 문자열 다루기 기본
[프로그래머스/자바스크립트(JavaScript)] 문자열 다루기 기본
2021.09.17 -
[프로그래머스/자바스크립트(JavaScript)] 수박수박수박수박수박수?
[프로그래머스/자바스크립트(JavaScript)] 수박수박수박수박수박수?
2021.09.17 -
[프로그래머스/자바스크립트(JavaScript)] 시저 암호
[프로그래머스/자바스크립트(JavaScript)] 시저 암호
2021.09.17