javascript怎麼算質數

質數是指只能被1和自身整除的正整數，是數學中的重要概念，在電腦科學中也有廣泛的應用。在Javascript中，我們可以使用以下幾種方法來計算質數。

1. 暴力枚舉法

暴力枚舉法是一種簡單直接的計算質數的方法。我們可以從2開始遍歷到n-1，依序判斷每個整數是否能夠整除n。如果存在一個整數m能夠整除n，則n不是質數。如果每個整數m都無法整除n，則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. Sieve of Eratosthenes

Sieve of Eratosthenes是一種更快速計算質數的方法。它的基本思想是先把所有正整數按順序排列，然後從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是一個合數，則至少有一半的小於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中計算質數的三種常用方法，不同的應用場景下可以選擇適合的方法來計算質數。

以上是javascript怎麼算質數的詳細內容。更多資訊請關注PHP中文網其他相關文章！