[에라토스테네스의 체]소수찾기

문제

문제 설명

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를 반환

 

문제풀이

https://choi95.tistory.com/50

뒤집은 소수

소수를 찾는 연산은 일전에 풀었던 뒤집은 소수 문제와 같았다.

 

코드

function isPrime(n) {
    for(let i = 2; i <= Math.sqrt(n); i++) {
        if(n % i === 0) return false;
    }
    return true;
}

function solution(n) {
    var answer = 0;
    for(let i = 2; i <= n; i++) {
        if(isPrime(i)) answer++;
    }
    return answer;
}

 

오답

테스트케이스 결과

정확도 테스트는 모두 다 맞쳤으나 효율성 테스트에서 시간 초과로 오답으로 처리되었다.

구글링해본 결과 에라토스테네스의 체를 사용하여 시간 복잡도를 줄여야만 효율성 테스트를 통과할 수 있는 문제였다.

 

에라토스네스의 체

• 주어진 숫자 값의 범위 안에서, 자기 자신을 제외한 배수 값을 삭제
• 위 연산 과정 후 소수만 남게 됨
• 입력 받은 숫자까지의 정수 중 소수의 개수를 구해야 할 경우에 용이

에라토스네스의 체

 

 

코드

let solution = (n) => {
    let arr = Array(n+1).fill(1).fill(0, 0, 2); //소수의 조건이 아닌 0과 1은 사전에 false

    for(let i=2; i*i<=n; i++){
        if(arr[i]){ //앞서 배수의 연산 과정에서 구해졌다면
            for(let j=i*i; j<=n; j+=i){ //배수 곱하기
                arr[j] = 0;
            }
        }
    }
    return arr.filter((e, _) => e).length;
}