用于检测素数的 JS 函数无法正常工作

Question

我正在尝试制作一个函数来确定一个数字在 JS 上是否为素数。我为此使用的方法是威尔逊定理，简而言之，如果 (num - 1)! % num 等于 num -1，则 num 是质数。为了实现这个功能，我制作了另一个函数来计算给定数字的阶乘。我还在 return false 中添加了一个条件运算符，如果给定的数字小于或等于 1，以满足质数的条件。

阶乘函数工作得很好（我检查了它的 return 值），但出于某种原因，威尔逊定理函数有问题。我研究了很多素数，确定低于 23 时该函数将起作用，而高于 29（23 之后的第一个素数）时该函数将不起作用（包括 29）。

现在，我知道有更简单的方法来实现用于此目的的函数，但我想尝试使用威尔逊定理，但真的不明白为什么这个函数不起作用。您可以在下面看到我的代码和我为该功能所做的测试。如果您注意到我的代码可能存在的任何问题，或者如果您知道我可以改进我的功能以达到更高的优化或解决我的问题，请发表评论。提前致谢。

// Factorial function
let factorial = function(num) {
  let outp = 1;
  for (let i = 1; i <= num; i++) {
      outp *= i;
  }
  return outp;
}

// Prime tester function
let isPrime = x => x <= 1 ? false : factorial(x-1) % x == x-1;

// Test function
console.log(isPrime(7));  // Should return: true, returns: true
console.log(isPrime(23));  // Should return: true, returns: true
console.log(isPrime(29));  // Should return: true, returns: false
console.log(isPrime(101));  // Should return: true, returns: false

如果相关，我正在使用 node.js，但我也在在线编译器上对其进行了测试，没有发现任何差异。

Answer 1

它对 29 和更大的数字不起作用的原因是 JavaScript 精度限制。 29！数字太大而无法存储，所以有点四舍五入。（对于更大的数字，它甚至可以是无穷大）。您可以将您的号码存储为字符串或数组。但是你必须自己实现乘法。

Answer 2

Javascript 的现代版本支持任意精度整数 (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt)，可用于精确计算大整数：

// Factorial function
let factorial = function (num) {
    let outp = 1n; // the `n` suffix indicates a `BigInt` constant
    for (let i = 1n; i <= num; i++) {
        outp *= i;
    }
    return outp;
}

// Prime tester function
let isPrime = x => x <= 1n ? false : factorial(x - 1n) % x == x - 1n;

// Test function
console.log(isPrime(7n));  
console.log(isPrime(23n)); 
console.log(isPrime(29n)); 
console.log(isPrime(101n));

用于检测素数的 JS 函数无法正常工作

JS function to detect primes not working correctly

javascript

node.js

function

primes

factorial