[알고리즘] 소수 찾기

문제

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

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

제한 조건
n은 2이상 1000000이하의 자연수입니다.

입출력 예시

n	result
10	4
5	3

---

나의 풀이 (실패)

function solution(n) {
    let count = n - 1 // 1은 소수 아님
    
    // 2부터 n까지의 탐색
    for(let i = 2; i <= n; i++) {
        // 2부터 n의 제곱근까지 나누어지는 수가 있는 지 확인
        for(let j = 2; j * j <= i; j++) {
            // 나누어진다면 소수가 아님
            if (i % j === 0 && i !== j) {
                count--
                break;
            }
        }
    }
    return count
}

위처럼 풀어 제출하니 정확성 테스트는 전부 통과하였으나, 효율성 테스트에서 시간 초과가 발생하였다.

2부터 n까지의 수(i)를 전부 다 탐색하는 동시에, 그 수(i)를 2부터 √n까지의 수(j)로 나누어 보며 소수인 지 판별하기 때문에 불필요한 연산이 많아 효율성 테스트에서 통과를 못한 것으로 보인다.

좀 더 효율적으로 소수를 찾기 위해 구글링을 해보니 에라토스테네스의 체를 이용하면 된다는 것을 알게 되었다!

부우운명히 옛날에 알고리즘 문제 풀 때, 들어 본 방법인데
막상 다시 보니까 또 초면 같아서 아예 그림으로 정리해보았다...🥲

---

📌 에라토스테네스의 체

n을 제외한 n의 배수는 소수가 될 수 없다는 원리를 사용한 방법!
⇒ n의 배수들은 n으로 나눠지기 때문에!

1부터 n 범위 안의 소수를 찾고자 할 때, √n 이하 수의 배수를 제거하고 남는 수는 모두 소수이다.

글로만 보면 이해가 될랑말랑한데, 그림을 보면 바로 이해가 가능하다!

✨ 에라토스테네스의 체를 이용한 풀이 (성공!)

function solution(n) {
    // 0과 1은 확실히 소수가 아니므로 false로 채워둔다. 나머지는 일단 소수라고 가정
    const arr = new Array(n + 1).fill(true, 2).fill(false, 0, 2);
    
    // n의 제곱근까지만 탐색
    for(let i = 2; i <= Math.sqrt(n); ++i){
        // 이미 제거된 인덱스는 건너뛰기
        if(arr[i] === false){
            continue; 
        }
        // i를 제외한 i의 배수를 제거
        for(let k = i * i; k <= n; k += i){
            arr[k] = false;
        }
    }
    
    // arr에 남아있는 true의 개수 === 소수의 개수
    const count = arr.filter(isPrime => !!isPrime).length
    return count;
}

---