문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result 10 4 5 3
풀이
function solution(n) {
//true = 소수
//각 인덱스가 해당 숫자의 소수여부를 나타냄
//ex) newArr[7] = true 는 숫자 7이 소수임을 나타낸다
let answer = 0;
let newArr = [];
//0부터 해당숫자까지 배열에 true로 주입하여 배열생성
for(let i = 0; i < n+1; i +=1) {
newArr.push(true);
}
//에라토스테네스의 체 이론
for(let i = 2; i*i<=n; i +=1){
if(newArr[i]){
for(let j = i*i; j <=n; j +=i){
newArr[j] = false;
}
}
}
//숫자 0 은 아무값도 아니므로 0으로 지정
newArr[0] = 0;
//숫자 1은 소수가 아니므로 false로 지정
newArr[1] = false;
answer = newArr.filter((el) => {
return el === true;
}).length;
return answer;
}
나무위키에 설명이 잘 되어 있는데 이를 간단히 설명하면 2부터 7까지(8부터는 2의 배수이므로)의 배수를 지우다 보면 소수가 남는 원리 이다.
처음에 이중반복문을 패기롭게 사용하고 패기롭게 시간초과가 떠서 이것저것 시도해보다 검색을 통해 알게된 이론이다.
- 하나의 수의 소수 여부를 판단하기 위해서는 약수의 존재여부를 판단하는데,
이 때는 제곱근이하의 숫자에 대해서 나눠지는지 알아보면 되는 꿀팁도 알게 되었다.(어차피 제곱근 위로는 제곱근의 밑에 해당하는 숫자에 곱하기 2가 대부분의 케이스이기 때문)
참고
ps
추가로 관련 수학지식을 쌓을 필요가 판단되면 추가하겠다 :)
알고리즘 풀이를 담은 블로그입니다.