반복문으로 소수판별

소수(Prime) : 1과 자기 자신 이외의 자연수로는 나눌 수 없는 자연수.

문제 : 1이상의 자연수를 입력받아 소수인지 여부 리턴

내가 처음에 접근한 방법

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

참 1차원적이다..
count라는 변수에 0을 할당해놓고,
i를 입력받은 num까지 반복하여 num % i === 0 이면 count +1
최종적으로 count가 2가 나오면 소수로 판별 (true)
아니면, 소수가 아님 (false)

하지만 이번에 배운 더 최적화된 코드.

function isPrime(num) {

  if (num === 2) {
    return true;
  }
  // 2인 경우 소수로 판별
  if (num % 2 === 0 || num === 1) {
    return false;
  }
  // 1이나 짝수인 경우 제외
  for (i = 3; i <= Math.sqrt(num); i = i + 2) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;

}

반복문이 핵심인데, 바로 에라토스테네스의 체 개념.
제곱근 이하까지의 약수까지만 검증하면 된다는 건데,

16 을 예로 들어보자
1 x 16
2 x 8
4 x 4
8 x 2
16 x 1

제곱근을 기준으로 대칭을 이루기 때문.

무튼 위 for반복문에서 i=3부터 2씩 증가인데,
이는 기존에 짝수를 제외했기 때문에, i는 홀수만 검증하면된다.
왜냐면 짝수 x 홀수 / 짝수 x 짝수 어느 경우든 짝수가 되기 때문.

이렇게 하면, 기존에 내가 쓴 코드보다 훨씬 효율적이고 계산이 빨라진다.