JavaScript에서 소수를 찾는 알고리즘은 무엇입니까?

소수는 1과 자기 자신으로만 나누어지는 양의 정수입니다. 소수를 찾는 알고리즘은 컴퓨터 과학에서 매우 기본적이고 중요한 문제이며, 암호화, 데이터 압축 등 다양한 분야에 적용될 수 있습니다.

JavaScript에서는 소수를 찾는 알고리즘을 구현하는 것이 매우 간단합니다. 아래에서는 두 가지 방법을 소개하겠습니다.

1. 소수 판단 방법

이 방법은 소수를 찾는 가장 기본적인 방법입니다. 그 원리는 양의 정수가 1과 자기 자신으로만 나누어질 수 있는지 여부를 판단하는 것입니다. 구체적인 구현 방법은 다음과 같습니다.

function isPrime(n) {
  if (n <= 1) {
    return false; // 1和0都不是素数
  }

  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false; // 如果n能被i整除，则n不是素数
    }
  }

  return true; // n是素数
}

이 함수는 양의 정수 n을 매개변수로 받습니다. n이 소수이면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 시간 복잡도는 O(n)이므로 최적이 아닙니다. 다수의 소수를 판단해야 하는 경우에는 아래 소개하는 에라토스테네스의 체를 사용하는 것이 좋습니다.

2. 에라토스테네스의 체

이 방법은 일련의 체를 거쳐 합성수를 제거하고 소수만 남깁니다. 구체적인 구현 방법은 다음과 같습니다.

function getPrimes(n) {
  let arr = new Array(n + 1).fill(true); // 先创建一个全为 true 的数组，代表是素数
  let primes = [];

  for (let i = 2; i <= n; i++) {
    if (arr[i]) {
      primes.push(i); // i 是素数，添加到 primes 数组中
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false; // 将 i 的倍数都标记为不是素数
      }
    }
  }

  return primes;
}

이 함수는 양의 정수 n을 매개변수로 받고 n보다 작거나 같은 소수의 배열을 반환합니다. 시간복잡도는 O(n log log n)로 소수판정법에 비해 빠르다.

결론

위는 JavaScript에서 소수를 찾는 두 가지 방법이지만 구현은 간단하지만 매우 실용적입니다. 소수에 관심이 있다면 이 두 가지 방법을 최적화하여 더 빠르고 효율적으로 만들 수 있습니다.

위 내용은 JavaScript에서 소수를 찾는 알고리즘은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!