소수를 판별하는 방법, 제곱근 나누기 [JavaScript]

소수란?

1과 자신이외의 수로는 나눠지지 않는 1보다 큰 양의 정수를 의미한다. ('1' 자신은 소수에서 제외한다.)

소수가 아닌 자연수들은 합성수라 부르며, 합성수는 1과 자신을 포함해 3개이상의 약수를 가진 수를 의미한다.

왜 제곱근을 기준으로 하는가?

소수인지 판별 할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나게 됩니다. 따라서 소수인지 판별할때는 그 자연수의 제곱근 이하의 수까지만 검사를 하면 됩니다. 검사할 데이터를 제곱근 개 이하로 줄일 수 있습니다.


예)
√24 를 기준으로 한다 할 때

2 * 12 | 3 * 8 | 4 * 6 | √24 * √24 | 6 * 4 | 8 * 3 | 12 * 2


JavaScript Code )

function isPrime(num) {
  if(num <= 1) { 
    // '1' 이하의 수눈 소수가 아닙니다.
    return false;
  }

  
  if(num % 2 === 0) { 
    // '2'는 짝수 중에 유일한 소수이며, 짝수는 '2'를 공통적으로 약수로 가지기 때문에 소수가 아닙니다.
    return num === 2 ? true : false;
  }

  
    
  for( let i = 3; i <= Math.sqrt(num); i += 2) {
    //Math.sqrt(num)로 제곱근을 계산하여 √num까지 나눠 떨어지는지 검사합니다.
    // '2'이하의 수들과 짝수들은 위의 조건문에서 걸러지기 때문에 '3'부터 '2'씩 올라며 '3'이상의 홀수들을 검사합니다.
    if(num % i === 0) {
    // num이  다른 수로 나눠 떨어진다면 그 수는 num의 약수입니다.
    // 이는 곧 '1'과 자신이외의 약수가 존재한다는 것이며, 이는 num이 소수가 아님을 의미합니다..
      return false;
    }
    return true;
    // 모든 조건문에서 걸리지지 않은 자연수는 소수입니다.
  }
}