[JavaScript] 소수 판별하기

1. 소수(Prime Number)란 무엇인가?

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

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

 

예를 들어,

2의 약수는 1, 2이므로 2는 소수이다.

3의 약수는 1, 3이므로 3은 소수이다.

4의 약수는 1, 2, 4이므로 4는 소수가 아니다.

5의 약수는 1, 5이므로 5는 소수이다.

...

 

 

2. 소수 판별하기

소수의 정의를 이용하면 어떤 수가 소수인지 판별할 수 있다. 어떤 수 N을 2, 3, ... , N-1로 나눴을 때 모두 나누어 떨어지지 않으면 N은 소수이다. 이를 JavaScript 코드로 표현해보자.

function isPrime(N) {
  // 1은 소수가 아니다.
  if (N === 1) return false;
  // 2부터 N-1까지의 수로 N을 나눴을 때
  for (let i = 2; i <= N - 1; i++) {
    // 나누어 떨어지는 경우가 한 번이라도 있으면 N은 소수가 아니다.
    if (N % 2 === 0) return false;
  }
  // 모두 나누어 떨어지지 않으면 N은 소수이다.
  return true;
}

 

 

3. 소수 판별하기 - Upgrade ✨

어떤 수 N의 약수는 항상 쌍으로 존재한다. 곱해서 N이 되는 짝꿍이 있다는 뜻!

 

예를 들어,

8의 약수는 1, 2, 4, 8이다. 1과 8, 2와 4를 곱하면 8이 된다.

9의 약수는 1, 3, 9이다. 1과 9, 3과 3을 곱하면 9가 된다. (3과 3도 쌍이라고 치자..)

 

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

 

따라서 어떤 수 N을 2, 3, ..., $\sqrt{N}$으로 나눴을 때 모두 나누어 떨어지지 않으면 N은 소수이다. 위의 소수 판별 방식보다 for문 반복 횟수가 줄어든다.

function isPrime(N) {
  // 1은 소수가 아니다.
  if (N === 1) return false;
  // 2부터 N제곱근까지의 수로 N을 나눴을 때
  for (let i = 2; i <= Math.sqrt(N); i++) {
    // 나누어 떨어지는 경우가 한 번이라도 있으면 N은 소수가 아니다.
    if (N % i === 0) return false;
  }
  // 모두 나누어 떨어지지 않으면 N은 소수이다.
  return true;
}