[javascript] 소수 판별식

1. 해당 숫자가 나누어질 때까지 반복문을 실행한다.

1 ) 먼저 소수는 2부터 시작이므로 num === 2 일 때는 return true이다.

2 ) 반복문이 끝나기 전에 num이 나누어지면 return false 나누어지지 않으면 return true이다.

3 ) 가장 간단하지만 시간복잡도가 가장 크다.

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

2. 해당 숫자의 가장 큰 약수 만큼 반복문을 실행한다.

1 ) 1번과 유사하지만 1번 보다 반복문을 반만 돌릴 수 있다. 약수는 해당 수의 반 이상을 넘어갈 수 없다.

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

3. 제곱근을 사용

1 ) Math.sqrt() 메소드를 사용하면 해당 수의 제곱근을 반환한다.

2 ) 예를들어 숫자 32가 있다. 32의 제곱근은 5.656854249492381이다.

  32의 약수는 1 2 4 8 16 32 가 있으며 1, 32를 제외하고 32를 만들 수 있는 식으로는 (2 * 16), (4 * 8), (8 * 4), (16 * 2) 네가지가 있다. 

  해당 수의 제곱근 보다 작은 약수에서 나눠지는 수가 안 나온다면 제곱근 보다 큰 수에서는 나눠지는 수가 나올 수가 없다.

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