소수 찾기

문제 링크

📩 문제 설명

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

제출 답안

// 처음 답안
function solution(n) {
    function isPrime(num) {
        if (num===1) return false;
        for (let i=2; i<num; i++) {
            if (num % i === 0) return false; 
        }
        return true;
    }
    
    let newArr = [];
    for (let i=1; i<=n; i++) {
        newArr.push(i)
    }
    return [...newArr.filter(v => isPrime(v))].length;
}

시간 초과 -> n은 1000000이하의 자연수.

시간을 더 줄일 방법을 고민하다가 결국 "에라토테네스의 체"를 사용하라는 팁을 보고 찾아봤다. 에라토테네스의 체란 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

이 알고리즘대로 그대로 코드를 작성하면 된다.

// 최종 답안
function solution(n) {
    let newArr = [];
    for (let i=2; i<=n; i++) {
        newArr.push(i);
    }
    
    let prime = [];
    for (let i=2; i<=n; i++) {
        if (newArr[i] === 0) continue;
        prime.push(i);
        newArr[i] = 0;
        
        for (let j=i*2; j<=n; j+=i) {
            if (newArr[j] === 0) continue;
            newArr[j] = 0;
        }
    }
    
    return prime.length;
}