[프로그래머스] 소수 찾기 (Javascript)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

 

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수를 만드시오.

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

제한 조건

• n은 2이상 1,000,000 이하의 자연수입니다. 

 

풀이

소수를 찾는 함수를 이용해 테스트 해본 결과 n의 크기가 너무 커서 시간 초과가 나왔다.

시간을 더 줄이고자 에라토테네스의 체 방식을 이용해 문제를 해결했다.

 

❌ Code - 실패 (시간 초과)

// 소수 찾는 함수
function find_prime(num) {        
    for (let i = 2; i <= num ** (1/2); i++) {
        if (num % i === 0) return false;
    }
    return true;
}

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

 

✅ Code - 성공

function solution(n) {
    var answer = 0;
    
    const 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 * 2; j <= n; j += i) {
            arr[j] = 0
        }
    }
    
    return arr.filter(e => e !== 0).length;
}

 

※ 참고

 

에라토테네스의 체 : 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는 간단하고 빠른 방법

1. 1 ~ n 까지의 숫자를 쭉 적는다.
2. 이 중에서 가장 작은 소수를 찾는다.
3. 가장 작은 소수의 배수를 전부 제거한다.
4. 다음으로 가장 작은 소수를 찾아 1 ~ 3번을 진행한다.