소수 판별하기

생각보다 문제를 풀다가 자주 사용되는 것으로 생각되어 정리를 해보기로 했다.

Hyunho NOH님의 블로그를 참고하였습니다.

원리는 다음과 같습니다. 확인하려는 수의 절반보다 더 큰 수에 대해서는 확인을 하지 않아도 됩니다. 예를 들어서 확인하려는 수가 14일 때, 절반인 7보다 큰 8, 9, 10, 11, 12는 절대 나누어 떨어지지 않습니다 !

$14 \div 7 = 2 ...\ 0$
$14 \div 8 = 1 ...\ 6$

1) 2로 나누어 떨어지지 않을 때

2) 3로 나누어 떨어지지 않을 때

...

N) $\sqrt N$로 나누어 떨어지지 않을 때

이렇게 되기 때문에 마지막 검사는 $\sqrt N$까지만 진행하면 됩니다.

소스코드

function isPrime(n) {
    if (n <= 1) {   // 1
        return false;
    }
    if (n === 2 || n === 3) {   // 2 or 3
        return true;
    }
    if (n % 2 === 0) {  // 2 * K
        return false;
    }
    let divisor = 3;
    let limit = Math.sqrt(n);   // 제곱근까지 반복문
    while (limit >= divisor) {  // 제곱근 >= 3
        if (n % divisor === 0) {    // 3,5,7,...의 배수인 경우
            return false;
        }
        divisor += 2;
    }
    return true;
}

1. 1일 때 false 반환한다.
2. 2 그리고 3일 경우에는 true를 반환한다
3. 짝수인 경우는 모두 false를 반환한다.
4. $\sqrt N$까지 3부터 나눠떨어지는 수가 있으면 false를 반환한다.
   4-1. 나눠주는 수는 짝수를 모두 제외했기때문에 +2씩 해준다.
5. 어떤것도 해당이 안된다면 true
   
   
   일반적으로 2로 나눈 수까지 검사를 진행하는 반면에 이렇게되면 연산횟수가 더 적어져서 유리할 것으로 예상된다.😁