소수(Prime Number) 판별

소수(Prime Number)란?

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 입니다.

위의 내용을 좀 더 잘 이해하기 위해 간단한 예시를 보겠습니다.

• 2의 약수는 1, 2 이므로 2는 소수입니다.
• 3의 약수는 1, 3 이므로 3은 소수입니다.
• 4의 약수는 1, 2, 4 이므로 4는 소수가 아닙니다.
• 5의 약수는 1, 5 이므로 5는 소수입니다.

소수 판별방법

첫번째 방법으로는 어떤 수 num을 2, 3, 4, ・・・ num-1 들의 숫자로 딱 맞아 떨어지지 않을 때 소수입니다.

이해가 잘 가지 않으시면 아래의 예시 코드를 봐주시면 됩니다.

function isPrime(num) {
    if (num === 1) return false;

    for(let i = 2; i < num; i++) {
        if (num % i === 0) return false;
    }

    return true;
}

위의 코드에서 true 값이 return 된다면 그 수는 소수입니다.

두번째 방법으로는 어떤 수의 제곱근을 이용하는 방법입니다.

어떤 수 num의 제곱근보다 작은 수에서 약수가 존재하지 않는다면, num의 제곱근보다 큰 수에서도 약수가 존재하지 않는다.

위의 정의대로 어떤 수 num을 2, 3, 4 ∙∙∙ √num 들의 숫자들로 딱 맞아 떨어지지 않을 때 소수입니다.

이번에도 이해가 잘 가지 않으시면 아래의 예시 코드를 봐주시면 됩니다.

function isPrime(num) {
    if (num === 1) return false;

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

    return true;
}

처음에 알려드린 방법과 다른 점은 어떤 수 num의 제곱근을 가지고 동일하게 반복문을 실행시키는 것 입니다.

위와 같은 방식으로 소수를 판별하게되면 처음 방법보다 반복문의 횟수가 줄어들기 때문에 더 좋은 방법이라고 할 수 있습니다.