时间戳

首页 > 解决方案 > 检测素数不能正常工作的 JS 函数

javascript - 检测素数不能正常工作的 JS 函数

问题描述

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

阶乘函数工作得很好（我检查了它的返回值），但由于某种原因，威尔逊定理函数有问题。我工作了很多素数，并确定低于 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，但我也在在线编译器上对其进行了测试，并没有发现任何差异。

标签： javascriptnode.jsfunctionprimesfactorial

解决方案

现代版本的 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));

推荐阅读