language: JavaScript

서론

특정 수가 소수인지 판별해내는 함수를 구현하고자 합니다.

소수가 무엇인지 알아봅시다.

소수(Prime Number) 란?
1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

( 참고로 합성수는 1보다 큰 자연수 중 소수가 아닌 수를 의미합니다. )

위를 통해 소수의 기준을 다음과 같이 정의할 수 있습니다.

• 1보다 큰 자연수
• 1과 자기 자신만이 약수

간단한 방법

소수 N 은 1 과 자기자신만을 약수로 가지므로, 2 ~ N-1 까지의 수로 나눴을 때 나머지가 0 이 아닙니다.

이를 이용해 간단한 소수 판별 함수를 만들 수 있습니다.

숫자 N을 2 부터 n-1 까지 나눴을 때 나머지가 0 인지 체크합니다.

function isPrimeNumber (input) {
  
  if (input <= 1) {
    return false;
  }
  
  for (let i=2; i<input; i++) {
    if (input%i == 0) {
      return false;
    }
  }
  
  return true;
}

• 시간 복잡도 O(N)

빠른 방법

소수 판별 함수를 더 빠르게 돌릴 수 있는 방법입니다.

√N 보다 더 큰 수는 합성수이거나 소수일 수 밖에 없습니다. (직접 해보면 이해됩니다)

따라서 숫자 N을 2부터 √N 까지 나눴을 때 나머지가 0 인지 체크합니다.

function isPrimeNumber (input) {
  
  if (input <= 1) {
    return false;
  }
  
  const sqrt = Math.sqrt(input);
  
  for (let i=2; i<=sqrt; i++) {
    if (input%i == 0) {
      return false;
    }
  }
  
  return true;
}

• 시간 복잡도 O(√N)

결론

특정 수가 소수인지 판별해낼 때는 두번째 방법이 더 빠릅니다.

+ 에라토스테네스의 체

• 에라토스테네스의 체 설명
• 특정 범위 내에서 소수를 찾을 때 가장 빠른 방법입니다.
• 하지만 특정 수가 소수인지 판별할 때는 속도가 매우 느려집니다.