[프로그래머스 lv.1] 소수 찾기 in javascript

G_New·2025년 3월 7일

js 코딩테스트

코딩테스트 with javascript

목록 보기

4/5

🐙 문제

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

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

제한 조건

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

입출력 예

n	result
10	4
5	3

✍️ 문제 풀이

쉬운 문제이지만, 시간 초과 문제로 어려움을 겪었던 문제

🔄️ 내가 생각한 문제 풀이 순서

1️⃣ 소수인지 판별하는 isDecimal(num)함수를 선언하기
2️⃣ isDecimal함수에서는 2부터 Math.sqrt(num) 까지 소수인지 검사하기
3️⃣ 2부터 n까지 소수인 숫자 개수를 파악하기

❎ 첫 코드 (실패 사유: 시간 초과)

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

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

이 코드를 사용할 경우 ⏰시간 초과 오류가 발생한다.

따라서, 이 문제를 해결하기 위해서는 에라토스테네스의 체를 사용해야 한다.

수학에서 에라토스테네스의 체는 소수를 찾는 빠르고 쉬운 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.

💡 에라토스테네스의 체

🔄️ 에라토스테네스의 체 활용 방법

🔽 내가 활용한 방법은 이렇다. ex) n = 10

1️⃣ 길이가 n+1 인 배열을 선언하고,
배열의 0번, 1번 인덱스에는 0으로, 나머지 인덱스에는 1으로 채운다.
ex) [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2️⃣ i = 2부터 차례대로 아래 방법을 적용한다.
- i번 인덱스의 값이 1이라면, i는 소수
  - i를 제외한 i의 배수 인덱스들의 값을 0으로 바꾼다.
    ex) i = 2일 때 2 제외 2의 배수 인덱스의 값을 0으로 바꾸기
    [0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0]
- i번 인덱스의 값이 0이라면, i는 소수가 아님 -> 건너뜀
3️⃣ 앞서 2️⃣를 모두 수행했으면 배열에는 소수 인덱스의 값만 1이고 나머지는 0이다.
따라서, 배열 안의 숫자들을 모두 합하면 소수의 개수를 구할 수 있다.

✅ 최종 코드

function solution(n) {
    let answer = 0;
    // 1️⃣ [0,0,1,1,...] 배열 만들기
    let arr = new Array(n+1).fill(0); // 길이가 n인 배열 0으로 채우기
    arr.fill(1,2) // 인덱스 2부터 1로 채우기
    
    // 2️⃣ i의 배수는 소수가 아니므로 0으로 바꾸기
    for(let i = 2; i <= n; i++){
        if(arr[i] === 0) continue;
        for(let j = 2*i; j <= n; j += i){
            arr[j] = 0;
        }
    }
    // 3️⃣ 소수 인덱스의 값은 1
    for(let n of arr){
        answer += n
    }
    return answer;
}

이처럼 에라토스테네스의 체를 사용하면 효율적으로 소수를 찾을 수 있다.