문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result
10 4
5 3입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
풀이
처음에는 중첩된 반복문을 이용해 합성수를 찾아서 제거하는 방식으로 풀었다.
3개의 테스트 케이스에서 시간이 너무 오래 걸려 실패했다.
function solution(n) {
let answer = n-1;
for(let i=2;i<=n;i++){
let num = 0;
for(let j=1;j<i;j++){
if(i%j == 0) num++;
if(num > 1){
answer--;
break;
}
}
}
return answer;
}입력값의 범위가 매우 넓기 때문에 모든걸 하나하나 찾으면 안되고, 보다 효율적인 방법을 생각해보아야 한다.
2,3,4,5,6,7,8,9,10,11
작은 수부터 배수를 제거해나가다보면 소수만 남지 않을까?
-> 2의 배수 제거, 3의 배수 제거, 5의 배수 제거,,
-> 구체적으로 어떻게 코드를 짜야할지 잘 모르겠어서 찾아보니 에라토스테네스의 체 알고리즘이란게 있었고, 혼자 생각해본 방식과 유사한 아이디어였다!
에라토스테네스의 체 알고리즘
-
2부터 N까지의 모든 자연수를 나열한다.
-
남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
-
남은 수 중에서 i를 제외한 i의 배수를 모두 제거한다.
-
더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다.
추가적인 개선책
여기에 더불어 n의 약수는 가운데 약수를 기준으로 대칭성을 보이고, 가운데 약수는 n의 제곱근을 넘지 않기 때문에 n까지가 아닌, n의 제곱근까지만 확인하면 된다는 성질을 추가하면 효율성을 더 높힐 수 있다.
ex. 16의 약수 : 1,2,4,8,16
에라토스테네스의 체 알고리즘을 이용해 n 이하의 소수의 갯수를 구해야할 때는 소수 여부를 확인하면 되므로 배열에 자연수를 세팅하는 것이 아닌 "true" & "false"로 세팅하면 된다. 이때, "true"는 소수를, "false"는 합성수를 나타낸다.
-
크기가
n+1인 배열을 만들고, "true"로 전부 채운다.
(index가 0부터 시작이라 실제 숫자와 위치를 맞추려면 0부터 n까지이기 때문에 n+1개로 세팅해야 한다.) -
0과 1은 소수가 아니기 때문에 미리 "false"로 지정한다.
-
2부터 n의 제곱근까지의 수들 중, 소수의 배수를 모두 "false"로 바꾼다.
-
"true"의 갯수만 세서 반환한다.
function solution(n) {
let arr = Array.from({length : n+1}).fill("true");
arr[0] = arr[1] = "false";
let sqrt = parseInt(Math.sqrt(n));
for(let i=2;i<=sqrt;i++){
if(arr[i] == "true"){
for(let j=2;i*j<=n;j++){
arr[i*j] = "false";
}
}
}
return arr.filter(el => el == "true").length;
}참고
