JavaScript - 소수 판별

주어진 숫자 number가 소수인지 아닌지 판별하는 단순한 코드

 

2부터 number까지의 숫자로 number를 나누어 보고 나머지가 존재하면 false를 반환하고, 나머지가 존재하는 경우가 없으면 true를 반환하는 함수

 

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

 

 

하지만 위 함수보다 더 효율적인 함수가 있다.

 

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

 

원리 : 에라토스테네스의 체

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전