我需要最快的程序来检查14位（或更大）数字的素数。我在多个网站上搜索过，但我不确定我找到的那些网站会使用与此类似的数字。
就主要测试而言，14位数字并不是很大。当数字具有一些特殊结构时，可能会有更快的专业测试（例如，如果它是一个梅森数），但一般来说，对该范围内数字的最快测试是
n最小素数，这样试验区只能用素数除以一次测试，只是避免测试除数（2除外）和3的倍数（除了3），足够好了。什么“小”意味着解释，截止100到10000之间的选择似乎是合理的，许多（很少）分裂仍然很快完成，他们找到了绝大多数的复合数字。n < 341,550,071,728,321是2,3,5,7,11,13和17-SPRP，那么n是素数”。快速确定性的通用初级测试，即APR-CL，ECPP，AKS，速度稍慢，实施起来要困难得多。对于14位或更多位数的数字，它们应该已经超过了纯粹的试验分区，但是比偶然发生的已知正确范围的概率测试慢得多。
但是，根据您的使用情况，最好的方法也可以是筛选连续的数字范围（例如，如果您想找到1014-109和1014之间的素数，筛子将比几亿快得多）快速个人主要测试）。
正如Daniel Fischer所说，14位数字对于素性测试并不是特别大。这给你几个选择。首先是简单的试验部门：
function isPrime(n)
d := 2
while d * d <= n
if n % d == 0
return Composite
d := d + 1
return Prime
10 ^ 14的平方根是10 ^ 7，因此可能需要一段时间。使用prime wheel更快一点：
struct wheel(delta[0 .. len-1], len, cycle)
w := wheel([1,2,2,4,2,4,2,4,6,2,6], 11, 3)
function isPrime(n, w)
d := 2; next := 0
while d * d <= n
if n % d == 0
return Composite
else
d := d + w.delta[next]
next := next + 1
if next == w.len
next := w.cycle
return Prime
这应该可以将天真的试验师加速2到3倍，这可能足以满足您的需求。
一个更好的选择可能是Miller-Rabin伪乱性测试仪。从强大的伪试验开始：
function isStrongPseudoprime(n, a)
d := n - 1; s := 0
while d is even
d := d / 2; s := s + 1
t := powerMod(a, d, n)
if t == 1 return ProbablyPrime
while s > 0
if t == n - 1
return ProbablyPrime
t := (t * t) % n
s := s - 1
return DefinitelyComposite
函数返回ProbablyPrime的每个a都是n的素数的见证：
function isPrime(n)
for a in [2,3,5,7,11,13,17]
if isStrongPseudoprime(n, a) == DefinitelyComposite
return DefinitelyComposite
return ProbablyPrime
菲舍尔指出，根据Gerhard Jaeschke的paper，对于n <10 ^ 14，这是完全可靠的。如果你想测试较大数字的素数，请随机选择25个证人。 powerMod(b,e,m)函数返回b ^ e（mod m）。如果您的语言不提供该功能，您可以像这样有效地计算它：
function powerMod(b, e, m)
x := 1
while e > 0
if e % 2 == 1
x := (b * x) % m
b := (b * b) % m
e := floor(e / 2)
return x
如果你对这个测试背后的数学感兴趣，我谦虚地在我的博客上推荐文章Programming with Prime Numbers。
循环变量'x'增加1，直到达到数字'num'的值。循环时使用modulo检查num是否可被x整除。如果余数为0，则停止。
防爆。
mod = 1;
while (mod != 0)
{
mod = num % x;
x++;
}
Tadah！素数检查器......不确定是否有比这更快的方法。
我最近做了一个更快的算法..它可以在几秒钟内轻松排出一个14位数字。只需将此代码粘贴到接受javascript代码并运行它的任何地方。请记住，javascript的版本必须是最新版本，因为它必须具有BigInteger支持才能执行这些操作。通常情况下，最新的浏览器（Chrome，Firefox，Safari）将支持这样的功能..但是，如果其他浏览器（如Microsoft IE）能够正确支持，那么任何人都可以猜测。
--
该算法通过结合使用前面提到的一些算法思想来工作。
然而...
该算法实际上是通过可视化素数集并将它们乘以各种不同的值然后对这些值执行各种mod操作并使用这些数字创建所有素数的3d表示来实现生成的，这些素数表示素数内存在的真实模式集。
var prime_nums = [2n,3n,5n,7n,11n,13n,17n,19n,23n,29n,31n,37n,41n,43n,47n,53n,59n,61n,67n,71n,73n,79n,83n,89n,97n,101n,103n,107n,109n,113n,127n,131n,137n,139n,149n,151n,157n,163n,167n,173n,179n,181n,191n,193n,197n,199n,211n,223n,227n,229n,233n,239n,241n,251n,257n,263n,269n,271n,277n,281n,283n,293n,307n,311n,313n,317n,331n,337n,347n,349n,353n,359n,367n,373n,379n,383n,389n,397n,401n,409n,419n,421n,431n,433n,439n,443n,449n,457n,461n,463n,467n,479n,487n,491n];
function isHugePrime(_num) {
var num = BigInt(_num);
var square_nums = [BigInt(9) , BigInt(25) , BigInt(49) ,BigInt(77) , BigInt(1) , BigInt(35) , BigInt(55)];
var z = BigInt(30);
var y = num % z;
var yList = [];
yList.push(num % BigInt(78));
var idx_guess = num / 468n;
var idx_cur = 0;
while ((z * z) < num) {
z += BigInt(468);
var l = prime_nums[prime_nums.length - 1]
while (l < (z / BigInt(3))) {
idx_cur++;
l += BigInt(2);
if (isHugePrime(l)) {
prime_nums.push(l);
}
}
y = num % z;
yList.push(y);
}
for (var i=0; i<yList.length; i++) {
var y2 = yList[i];
y = y2;
if (prime_nums.includes(num)) { return true; }
if ((prime_nums.includes(y)) || (y == BigInt(1)) || (square_nums.includes(y))) {
if ((y != BigInt(1)) && ((num % y) != BigInt(0))) {
for (var t=0; t<prime_nums.length; t++) {
var r = prime_nums[t];
if ((num % r) == BigInt(0)) { return false; }
}
return true;
}
if (y == BigInt(1)) {
var q = BigInt(num);
for (var t=0; t<prime_nums.length; t++) {
var r = prime_nums[t];
if ((q % r) == BigInt(0)) { return false; }
}
return true;
}
}
}
return false;
}