728x90
소수 찾기는 에라토스테네스의 체를 통해 쉽게 풀 수 있다.
에라토스테네스의 체를 간단하게 설명하자면 2부터 N까지 자신의 배수들을 지워가면 결국 소수들만 남는다.
이를 이용하여 소수 찾기 문제를 간단하게 해결할 것이다.
문제
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
풀이
function solution(n) {
let answer = 0;
let arr = [];
for(let i = 2; i <= n; i++){
arr[i] = i;
}
for(let i = 2; i <= n; i++){
if(arr[i] === 0) continue;
for(let j = i+i; j <= n; j+=i){
arr[j] = 0;
}
}
for(let i = 2; i <= n; i++){
if(arr[i] !== 0) answer++;
}
return answer;
}
320x100
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[자바스크립트/알고리즘] 프로그래머스 - 두 개 뽑아서 더하기 (0) | 2021.01.25 |
---|---|
[자바스크립트/알고리즘] 프로그래머스- 신규 아이디 추천 (카카오 2021 블라인드 채용 문제) (0) | 2021.01.25 |
[자바스크립트/알고리즘] 프로그래머스-모의고사 (0) | 2021.01.24 |
[자바스크립트/알고리즘] 프로그래머스-콜라츠 추측 (0) | 2021.01.23 |
[자바스크립트/알고리즘] 프로그래머스 - 하샤드 수 (0) | 2021.01.23 |