[프로그래머스][JS] 소수 찾기 ✅

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

프로그래머스

풀이 과정

function solution(n) {
    // 길이가 n만큼 요소를 생성하고 true로 채우기 
    const isPrime = Array(n + 1).fill(true)
    // 0과 1은 소수가 아니기 때문에 false로 바꾸기
    isPrime[0] = isPrime[1] = false

    // 소수 판별
    for (let i = 2; i <= Math.sqrt(n); i++){
        if(isPrime[i]){ // true인 경우만 (0과 1을 제외한 모든 수)
            // i = 2인 경우, j = 4, 6, 8, ... j모두 소수가 아니므로 false
            // i = 3인 경우, j = 9, 12, 15 ... 위와 동일
            // j가 i * i인 이유 : i가 3일 때 j를 i이라고 하면 3, 6, 9... 이렇게 되는데 
            // 6의 경우는 i = 2일 때 2의 배수로 이미 false처리를 해줬다. i * i를 해서 중복 계산을 하지 않아 성능 향상
            for (let j = i * i; j <= n; j += i){ // 해당 배수들은 전부 소수가 아니기 때문에 false
                isPrime[j] = false 
            }
        }
    }
    // true인 경우만 필터링
    let cnt = isPrime.filter(item => item).length
    return cnt
}

 

제곱근과 배수를 함께 사용하여 소수를 찾는 것이 에라토스테네스의 체 알고리즘이다.

제곱근만 사용하여 소수를 판별할 수 있지만 동일한 연산을 반복하기 때문에 시간이 오래 걸린다. 

---

리뷰

// 틀린 코드
function solution(n) {
    // 2부터 n까지 numbers에 생성 -> 1은 소수가 아니기 때문에 처음부터 제외
    // {length : n - 1} : 배열의 길이가 n - 1 
    // (_, index) => index + 2 : '_'는 생성되는 요소의 값, index는 생성되는 요소의 값의 인덱스
    // 인덱스는 0부터 시작하는데 원하는 요소의 값은 2부터니까 '인덱스 + 2' 해야 한다
    const numbers = Array.from({length : n - 1}, (_, index) => index + 2) 
    // console.log(numbers)
    let cnt = 0
    for (let i = 0; i < numbers.length; i++){
        let prime = true
        const num = numbers[i]
        // 해당 요소의 제곱근을 구하여 2부터 제곱근까지 나누어 떨어지면 소수가 아님
        for (let j = 2; j <= Math.sqrt(num); j++){
            if (num % j === 0){
                prime = false
                break
            }
        }
        if (prime){ // 소수인 경우에 +1
            cnt++
        }
    }
    return cnt;
}

첫 시도 때 위의 코드처럼 풀었더니 시간초과가 발생해서 틀렸는데 위의 코드같은 경우는

소수 판별하는 과정이 너무 오래걸리기 때문이다. 그래서 에라토스테네스 체 알고리즘을 사용하여 연산을 줄여줘야 한다.  

 

2023.07.16 - [Programmers] - [프로그래머스][JS] 소수 만들기

에라토스테네스 체 알고리즘 문제를 '소수 만들기' 문제에서 풀어서 똑같이 풀었는데

에라토스테네스 체 알고리즘을 제곱근으로만 푸는 알고리즘이라고 잘못 알아서 시간 초과가 발생했었다.

'제곱근 + 배수' 함께 사용해야하는것 잊지 말기!!

진짜 이 정도면 다음번 소수문제는 꼭 맞춰야...