[알고리즘]primeTester - 소수 판별

왜 제곱근까지만 루프를 돌면 알고리즘의 복잡성을 줄일 수 있을까?

var primeTester = function(n) {
  if (typeof n !== "number" || n < 1 || n % 1 !== 0) {
    // n isn't a number or n is less than 1 or n is not an integer
    return false;
  }

  if (n === 1) {
    return false;
  }
  // TODO: return true if n is prime, false otherwise
  // 2 => 1,2
  // 3 => 1,3
  // 5 => 1,5
  // 6 => 1,2,3,6 (x)
  // 7 => 1,7
  // 숫자의 제곱근까지 루프를 실행하면 알고리즘의 복잡성을 O (n)에서 O (sqrt (n))로 줄일 수도 있다.
  // 참고 : https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript
  let num = Math.sqrt(n);

  for (let i = 2; i <= num; i++) {
    // console.log("나머지가 0이 아닌것들 ?? ", i);
    if (n % i === 0) {
      return false;
    }
  }
  return true;
};

참고블로그

• https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript
• https://www.thepolyglotdeveloper.com/2015/04/determine-if-a-number-is-prime-using-javascript/
• 위키백과 - 에라토스테네스의 체