[프로그래머스 JS] 소수 찾기 : 에라토스테네스의 체

문제

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예nresult

10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

풀이 과정

1. 자기자신이 아닌 수로 나누어떨어지면 소수가 아니라고 판별하는 함수를 만들어 작성했는데, 효율성 검사에서 시간초과가 떴다. 아마 숫자가 커지면 시간이 오래 걸려서 그런 것 같다.
2. 제곱근(Math.sqrt)사용하기 : 그 수의 제곱근보다 작은 수에서 나눠지는 수가 안나오면 그 수의 제곱근보다 큰 수에서도 나눠지는 수가 나올 수 없어 굳이 제곱근보다 큰 수까지 반복문을 돌릴 필요가 없다고 한다. 그렇지만 이 방법도 효율성 검사에서 시간 초과가 떴다.
3. 에라토스테네스의 체를 써야 한단다..... 중학교땐가 배운 거 같은데.. 수학 망했으면 좋겠다. 

 

---

 

사용한 메서드

• fill : 배열을 채울 수 있다.

---

전체 코드

function solution(n) {
    var answer = isSosu(n);
    return answer;
}

function isSosu(n){
    let arr = Array(n+1).fill(true).fill(false, 0, 2);
    for (let i=2; i*i<=n; i++){
        if(arr[i]){
            for(let j=i*i; j<=n; j+=i){
                arr[j] = false;
            }
        }
    }
    return arr.filter(e => e).length;
}