JavaScript에서 숫자가 소수인지 효율적으로 확인하는 방법은 무엇입니까?

JavaScript에서 소수 확인

이 문서에서는 주어진 숫자가 소수인지 여부를 JavaScript를 사용하지 않고 결정하는 문제를 다룹니다. 소수는 1과 자기 자신을 제외한 다른 자연수로 나누어지지 않는 1보다 큰 정수입니다.

해결책 1

전통적인 방법은 2에서 반복하는 것입니다. 입력 숫자의 제곱근에 숫자가 이들 중 하나로 나누어지는지 확인합니다. 그렇다면 소수가 아닙니다. 그렇지 않으면 그렇습니다.

<code class="javascript">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true; // because 1 is not prime

for (let i = 2; i < inputValue; i++) {
  inputValue % i == 0 ? (isPrime *= false) : (isPrime *= true);
}

alert(`${inputValue} is ${isPrime ? 'prime' : 'not prime'} number`);

시간 복잡도: O(sqrt(n))
공간 복잡도: O(1)

해결책 2

대체 접근 방식은 2보다 큰 소수는 홀수일 수 없다는 사실을 활용합니다. 따라서 2로 나눈 다음 입력된 숫자의 제곱근까지 홀수로 나누어 확인하는 것으로 충분합니다. 이 최적화를 통해 실행 시간이 크게 단축됩니다.

<code class="javascript">const isPrime = num => {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 == 0 || num % 3 == 0) return false;
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) return false;
  }
  return true;
};</code>

시간 복잡도: O(sqrt(n))
공간 복잡도: O(1)

위 내용은 JavaScript에서 숫자가 소수인지 효율적으로 확인하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!