프로그래머스 | 소수 구하기

📌 문제

자연수 n이 있을 때 해당 자연수가 1과 자기 자신으로만 나누어지는지에 대한 여부를 출력하는 코드를 작성하세요.
이때 n은 1보다 크고 10,000,000보다 작습니다.

✨ 해결 방법

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다.
소수를 판별하는 방법은 여러 가지가 있으며, 그 중 한 가지는 반복문을 활용하는 것입니다.

💻 solution

function solution(n) {
    var answer = true;
    if (1<n<=10000000){
        for(let i=2; i<=Math.floor(Math.sqrt(n)); i++){
            if (n % i === 0) {
                answer = false;
                break;
                }
        }
    }
    return answer;
}

for문을 활용하여 2부터 n의 제곱근을 정수로 변환한 값보다 작을 때까지 반복하여 검사를 합니다. n을 해당 수로 나눴을 때 나누어 떨어지면 여부를 false로 바꾸고 반복문을 멈추고, 아닐 경우 계속 true로 두게 됩니다.

i<=Math.floor(Math.sqrt(n)); 부분을 더 해설하기 전에, 두 가지의 과정을 먼저 거치며 이해를 할 필요가 있습니다.

i < n

우선 소수는 단순히 자연수 미만까지 검사하여 구할 수 있습니다.
만약 코드가 아래와 같이 작성되어 있다면, 이는 2부터 n 미만인 수까지 검사를 하게 되므로 문제가 없습니다.

function solution(n) {
    var answer = true;
    if (1<n<=10000000){
        for(let i=2; i < n; i++){
            if (n % i === 0) {
                answer = false;
                break;
                }
        }
    }
    return answer;
}

i <= n / 2 (최대공약수)

하지만 약수에 대해 잘 생각해보면 범위를 줄일 수 있습니다.
8의 약수는 1,2,4,8 / 10의 약수는 1,2,5,10인 것처럼 최대공약수는 나누고자 하는 수의 절반을 초과할 수 없습니다. 따라서 범위는 아래와 같이 좁혀 작성이 가능합니다.

function solution(n) {
    var answer = true;
    if (1<n<=10000000){
      // 혹은 i*i <= n;
        for(let i=2; i <= n / 2; i++){
            if (n % i === 0) {
                answer = false;
                break;
                }
        }
    }
    return answer;
}

i <= Math.floor(Math.sqrt(n)) (제곱근)

여기서 더 나아가서, 범위를 제곱근으로 더 좁힐 수도 있습니다.

어떤 수의 약수는 무조건 짝으로 존재하게 됩니다. 1과 어떤 수가 짝이고, 그 내부에 양 끝에서 하나씩 서로 짝을 이루게 됩니다.
따라서 만약 어떤 약수 a를 검사한다면, 반대편 짝인 b은 검사하지 않아도 무관합니다.

또한 이 경우 a와 b 중 적어도 하나는 제곱근 이하의 값이 되므로 제곱근을 초과하는 수는 검사할 필요가 없는 것입니다.

---

Math.sqrt(n) 함수는 n의 제곱근을 계산합니다.
그런데 해당 숫자가 제곱수( 제곱근이 정수로 정확하게 떨어지는 수 : 4, 9, 16, 25 등..)가 아니라면 그 결과는 부동 소수점 수일 가능성이 높습니다. 하지만 for 반복문의 조건은 정수를 사용하기 때문에, Math.floor를 사용하여 정수 부분을 추출하여 제곱근 값을 정수 형태로 비교해야 합니다.

parseInt도 가능하지만, 이는 주로 문자열에서 숫자를 추출하는데 주로 사용되고, 소수를 내림하는 역할로는 Math.floor, 혹은 Math.ceil 을 사용하는 것이 더 정확합니다.