[Programmers] 소수 찾기(JavaScript)

 

알림

 

본 포스팅은 공부 목적으로 작성된 글이며 상업적 목적으로 절대 사용되지 않았음을 밝힙니다.

 

문제

 

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

프로그래머스

 

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

 

코드

 

function isPrime(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(isPrime(i)) answer++;
    }
    return answer;
}

 

풀이

 

이전에 풀었던 소수 만들기와 비슷하게 접근했는데요. 소수임을 판별하는 함수를 생성한 뒤, 받아오는 숫자만큼 반복문을 돌려 함수에 매개변수로 전송해 소수일 시, 정답을 카운트 해 이를 리턴해주면 됩니다.

 

2022.07.29 - [Algorithm/Programmers] - [Programmers] 소수 만들기(JavaScript)

[Programmers] 소수 만들기(JavaScript)

 

하지만 이전에 풀이했던 대로 함수를 작성하게 되면 정확성 테스트의 일부는 시간 초과를 하게 되고, 효율성 테스트 또한 통과하지 못하는데요. 이런 경우는 대개 끝의 테스트 케이스에서 매우 큰 숫자에서 통과를 못하는 등, 코드가 비효율적이란 의미이기 때문에, 현재 로직은 유지하고 다른 부분을 수정하기로 했습니다.

 

그러다 마침 저를 포함한 효율성 테스트를 통과하지 못하는 사람들을 위한 조언 글을 발견하게 되었고, 해당 글은 트러블 슈팅을 하기엔 충분했습니다. 내용은 다음과 같습니다.

 

1보다 큰 모든 자연수는 소수의 곱으로 이루어져 있고, 저를 포함한 대부분의 사람들은 소수를 구하기 위해 2부터 차례대로 증가시켜 입력 받은 수를 일일이 나눠보는 방법을 택한다는 것이죠.

그러나 이는 매우 비효율적인 방법이며, 앞서 말한 것처럼 1보다 큰 자연수는 소수의 곱으로 이루어져 있기 때문에 소수로만 나누면 된다고 쉽고 빠르게 구할 수 있다고 합니다.

 

예를 들어, 10이 소수인지 아닌 알기 위해선 9개의 수가 아닌 10보다 작은 소수 4개만 이용하면 되는 거고, 받아오는 수가 100으로 커진다면 99개의 자연수가 아닌 25개의 소수만 이용하면 되는데요.

 

이어서 어떤 자연수 n이 있을 때 √n보다 작은 모든 소수들로 나누어 떨어지지 않으면 n은 소수라고 말하는데, 해당 개념과 위에서 설명한 개념을 같이 적용시켜 예를 들면, 101이 소수인지 아닌지 판별하기 위해선 우린 √101을 구하여 해당 수보다 작은 소수로 나눠보면 된다는 것입니다.

 

실제로 √101은 10.xxx가 나올 것이고, 자연수 10보다 작은 수는 2, 3, 5, 7로 나눴을 때 나누어 떨어지지 않으므로 101은 소수임을 알 수 있고, 기존에 제가 접근한 대로였으면 101보다 작은 수를 전부 구했을 텐데, 10번으로 줄일 수 있었고 이는 해당 문제의 효율성 테스트를 통과시켜주는 중요한 힌트가 되었습니다.

 

돌아보며 해당 문제는 로직을 짜는 것도 중요하지만 효율적인 코드를 잘 작성할 수 있는지도 파악할 수 있는 문제였던 것 같습니다.