제곱근(square root, sqrt)과 소수 구하기🤓

JavaScript를 공부하며 문제를 풀던 도중 뇌에 렉걸리는 문제를 만나게 되었다. 본문의 코드는 코딩 왕초보의 풀이이므로 가성비 개쩌는 이상적인 클린 코드가 아닌 점을 참고해주시길 바란다...

2 이상의 자연수를 입력받아 2부터 해당 수까지의 소수(prime number)들을 리턴해야 한다.

1. 입력
   argument 1: Number 타입의 정수(num >= 2)

2. 출력
   - String 타입을 리턴해야 한다.
   - '2-3-5-7'의 형식으로 리턴해야 한다.

function listPrimes(num) {
  // result에는 항상 '2'가 포함된다.
  let result = '2';
  
  // 3부터 num까지의 홀수 중에서 소수 찾기
  for(let i = 3; i <= num; i += 2){
    let isPrime = true;
    // num의 약수 중 제곱근num보다 큰 수는 고려할 필요가 없다
    let sqrt = parseInt(Math.sqrt(i));
    for(let j = 3; j <= sqrt; j += 2){
      // 3 ~ num 사이의 수가 sqrt이하의 홀수로 나누어 떨어지면 그 수는 소수가 아니다.
      if(i % j === 0){
        isPrime = false;
        break;
      }
    }
    if(isPrime){
      result = result + `-${i}`;
    }
  }
  return result;
}
debugger; listPrimes(12);

처음 sqrt를 포함해야 큰 수를 입력 했을 때 컴퓨터가 지쳐 쓰러지지 않는다는 것을 알고나서 저 sqrt라는 것을 이해하기 위해 조금 고생을 했다.

검색해서 알아보면 쉽게 알 수 있었겠지만 내 손으로 내 뇌로 이해하고 싶었기에 손코딩에 디버깅에 온갖 가정을 해서 써보았다.

그래서 이해한 결과 Math.sqrt()를 사용해야 하는 이유는
'num의 약수 중 제곱근num보다 큰 수부터는 고려할 필요가 없기 때문이다'라는 결론이 나왔다.

예를 들어

num이 16이라고 가정했을 때
num의 약수는 1, 2, 4, 8, 16이다.
Math.sqrt(num)은 4이고 4보다 큰 약수는
제곱근 num보다 작은 수와 곱해야 하는 수이기 때문에
이미 이전에 고려되었다고 확신할 수 있다.

따라서 num이 소수인지 판별하기 위해 제곱근num보다 큰 약수가 존재하는지는 고려할 필요가 없다!