[JS] 소수 판별 구현하기

소수(Prime number)

• 1과 자기 자신만으로 나누어 떨어지는 정수
• 1과 음수는 소수가 아님

반복문으로 구현 ( $O(n)$ )

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

제곱근 이용한 구현 ( $O(\sqrt n)$ )

function isPrime(num) {
  if(num <= 1) { 
    return false;
  }

  if( num % 2 === 0) { 
    return num === 2 ? true : false;
  }
   
  const sqrt = parseInt(Math.sqrt(num));

  for( let divider = 3; divider <= sqrt; divider += 2) {

    if(num % divider === 0) {
      return false;
    }
    
  }
  
  return true;
}

에라토스테네스의 체 ( $O(nlog(logn))$ )

function solution(n) {
  let arr = Array(n + 1).fill(true).fill(false, 0, 2)

  // i : n의 제곱근까지 loop
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (arr[i]) {
      // i의 배수 false로 변경
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false;
      }
    }
  }
  return arr
}