자바스크립트에서 소수를 계산하는 방법

소수는 1과 자기 자신으로만 나누어질 수 있는 양의 정수를 의미하며 수학에서 중요한 개념이며 컴퓨터 과학에서 널리 사용됩니다. Javascript에서는 다음과 같은 방법을 사용하여 소수를 계산할 수 있습니다.

1. 폭력적인 열거법

폭력적인 열거법은 소수를 계산하는 간단하고 직접적인 방법입니다. 2에서 시작하여 n-1로 이동하여 각 정수가 n을 나눌 수 있는지 확인할 수 있습니다. n을 나누는 정수 m이 있으면 n은 소수가 아닙니다. n이 모든 정수 m으로 나누어지지 않으면 n은 소수입니다.

다음은 무차별 열거 방식의 Javascript 구현 코드입니다.

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

2. 에라토스테네스의 체

에라토스테네스의 체는 소수를 계산하는 더 빠른 방법입니다. 기본 아이디어는 먼저 모든 양의 정수를 순서대로 정렬한 다음 2로 나눌 수 있는 숫자를 2부터 필터링하고, 그런 다음 3으로 나눌 수 있는 숫자를 필터링한 다음, 나눌 수 있는 숫자를 필터링하는 것입니다. 더 이상 소수가 필터링될 수 없을 때까지 5만큼 계속됩니다.

다음은 Sieve of Eratosthenes의 Javascript 구현 코드입니다.

function sieveOfEratosthenes(n) {
  const primes = new Array(n + 1).fill(true);

  primes[0] = false;
  primes[1] = false;

  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes.reduce((acc, cur, index) => {
    if (cur) {
      acc.push(index);
    }

    return acc;
  }, []);
}

3. Miller-Rabin 알고리즘

Miller-Rabin 알고리즘은 중요한 정리를 기반으로 하는 확률적 소수 테스트 알고리즘입니다. n이 합성인 경우 number 이면 n보다 작은 양의 정수 a 중 적어도 절반이 a^(n-1) mod n != 1을 충족합니다. Miller-Rabin 알고리즘의 핵심은 주어진 정수 n에 대해 k개의 무작위 테스트를 수행하고 이를 사용하여 n이 소수인지 여부를 결정하는 것입니다. 일반적으로 보다 정확한 결과를 얻으려면 15-20번의 테스트만 필요합니다.

다음은 Miller-Rabin 알고리즘의 Javascript 구현 코드입니다.

// 快速幂算法
function powerMod(a, b, m) {
  let res = 1;

  while (b) {
    if (b & 1) {
      res = (res * a) % m;
    }

    a = (a * a) % m;
    b >>= 1;
  }

  return res;
}

function isPrime(num, k) {
  if (num < 2) {
    return false;
  }

  if (num === 2 || num === 3) {
    return true;
  }

  let d = num - 1;
  let r = 0;

  while (d % 2 === 0) {
    d /= 2;
    r++;
  }

  for (let i = 0; i < k; i++) {
    const a = 2 + Math.floor(Math.random() * (num - 3));
    let x = powerMod(a, d, num);

    if (x === 1 || x === num - 1) {
      continue;
    }

    let flag = false;

    for (let j = 1; j < r; j++) {
      x = (x * x) % num;

      if (x === num - 1) {
        flag = true;
        break;
      }
    }

    if (!flag) {
      return false;
    }
  }

  return true;
}

위는 Javascript에서 소수를 계산하는 세 가지 일반적인 방법입니다. 다양한 응용 시나리오에서 소수를 계산하는 데 적합한 방법을 선택할 수 있습니다.

위 내용은 자바스크립트에서 소수를 계산하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!