소수 판별

소수는 약수가 1과 본인 자신만을 가짐

 

1. 반복문 사용 (1과 본인 제외 약수가질시 false)

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

 

2. 제곱근 사용

예를들어 16의 약수는

1, 2, 4, 8, 16이 있는데

16은 1*16, 2*8, 4*4이다

제곱근인 4까지만 계산해보면 그 뒤는 8*2, 16*1처럼 자리 위치만 반전되는것이라 제곱근까지만 계산해도 된다

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

 

3. 에라토스테네스의 체

2부터 n까지 배수들을 지우다보면 소수만 남음

function isPrime(num) {
  if(num <= 1) {
    return false;
  }
  //짝수중 2는 유일한 소수
  if( num % 2 === 0) { 
    return num === 2 ? true : false;
  }
  
  const sqrt = parseInt(Math.sqrt(num));

  for( let i = 3; i <= sqrt; i += 2) {
    if(num % i === 0) {
      return false;
    }
  }
  
  return true;
}