枚举大(20位)[可能]素数

Question

给定A，在10^20的数量级上，我想快速获得大于A的前几个质数的列表。好的，我的需求并不是很精确-如果列表中偶尔出现一个复合数字也没问题。

枚举大于A的(可能)素数的最快方法是什么？

有没有比遍历所有大于A的整数(除了2和3的明显倍数)并对每个整数执行质数测试更快的方法？如果不是，唯一的方法是测试每个整数，我应该使用什么质数测试？

Answer 1

有没有比遍历所有大于A的整数(除了2和3的明显倍数)并对每个整数执行质数测试更快的方法？

不，如果没有素性测试，就无法知道一个数是否为素数。

但是，您可以非常快速地对任何数字执行概率素数测试，如Miller-Rabin。这是一种安全且被广泛接受的寻找大素数的方法。由于素数相对丰富，因此使用此方法在任何范围内查找素数都不会有问题。只需使用一个经过测试且高效的Miller-Rabin实现，就可以了。

Answer 2

你能做的最好的事情就是生成一个合理的候选者，然后对其进行测试。Miller-Rabin测试满足您的要求，即给出一个数字为质数的高概率，并且您可以根据您使用的迭代次数，将组合滑落到或多或少的任意级别的可能性降低。

Answer 3

素数是非常频繁的数。素数的频率是log(n)，这意味着平均每个46个数都是素数，其中n=10^20。这意味着检查每个数字的素性不是这样的开销。