[JavaScript] 소수 판별하기

소수란?

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
즉, 1보다 큰 자연수 중 1과 자기 자신을 제외한 어떤 수로도 나누어 떨어지지 않는 수를 뜻한다.

소수를 구하는 방법

앞서 말한 소수의 정의를 이용하여 소수를 판별하려 한다. 어떤 수 num을 2, 3, ... , num-1로 나눴을 때 모두 나누어 떨어지지 않으면 N은 소수가 된다.

function isPrime(num) {
  if (num === 1) return false;  // 1은 소수가 아님
  for (let i = 2; i <= num - 1; i++) {  // 2부터 num-1까지의 수로 num을 나눈경우
    if (num % 2 === 0) return false; // 나머지가 0이면
  }
  return true; //나눠지지 않으면 num은 소수이다.
}

소수를 구하는 방법(제곱근)

✅ 어떤 수 num의 약수는 항상 쌍으로 존재 --> 곱해서 num 한 쌍이 있다는것을 뜻한다.

ex)

8의 약수(1, 2, 4, 8)이다. 1 x 8, 2 x 4를 곱하면 8이다.

9의 약수(1, 3, 9)이다. 1 x 9, 3 x 3을 곱하면 9이다.

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

따라서 num을 2, 3, ..., √num으로 나눴을 때 나누어 떨어지지 않으면 num은 소수이다.

function isPrime(num) { // 1은 소수 x
  if (num === 1) return false; // 2부터 num제곱근까지의 수로 num을 나눈 경우
  for (let i = 2; i <= Math.sqrt(num); i++) {	// 나눠지는 경우가 한 번이라도 있으면 num은 소수 x
    if (num % 2 === 0) return false;
  }
  return true;  // 나눠지지 않으면 num은 소수
}

더 정확한 판별이 가능하다.