이번에는 반복문을 이용하여 소수를 판별하는 알고리즘을 개선하는 방법에 대해 알아보겠습니다.

기존 알고리즘

기존의 소수 판별 알고리즘은 대개 소수를 판별할 숫자 n이 주어졌을 때 2부터 n-1까지 모든 수로 n을 나눠보는 방식입니다. 이 방법은 비효율적이며, 불필요한 반복을 수행하므로 개선이 필요합니다.

개선된 알고리즘

우리가 개선할 알고리즘은, 2부터 n의 제곱근까지만 나눠보는 방식입니다. 제곱근까지만 나눠봐도 나머지 수는 계산하지 않아도 됩니다.

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

위의 코드에서 Math.sqrt(n)을 이용하여 n의 제곱근까지만 반복하도록 하였습니다. 이를 통해 불필요한 반복을 줄일 수 있고, 알고리즘의 성능을 향상시킬 수 있습니다.

마치며

이렇게 반복문을 이용한 소수 판별 알고리즘을 개선하는 방법에 대해 알아보았습니다. 적절한 알고리즘을 선택하고, 코드를 개선함으로써 성능을 향상시킬 수 있습니다.

참고문헌: MDN web docs - Math.sqrt()