问给定素数N，计算下一个素数？

EN

众所周知，gaps between consecutive prime numbers非常小，质数370261出现了第一个超过100%的差距。这意味着即使是一个简单的蛮力在大多数情况下也足够快，平均需要O(ln(p)*sqrt(p))。

对于p=10,000，这是O(921)操作。请记住，我们将在每次O(ln(p))插入(粗略地说)时执行一次，这完全符合大多数现代硬件上毫秒量级的大多数问题的约束。

以防有人好奇：

使用reflector I确定.Net使用一个静态类，它包含一个硬编码的~72个素数列表，范围最大为7199369，它扫描至少是当前大小的两倍的最小素数，对于大于当前大小的最小素数，它通过尝试除以所有奇数直到潜在数的sqrt来计算下一个素数。这个类是不可变的，并且是线程安全的(即较大的素数不会被存储起来以备将来使用)。

一个很好的技巧是使用部分筛子。例如，数字N= 2534536543556后面的下一个质数是什么？

检查N相对于一列小素数的模数。因此...

mod(2534536543556,[3 5 7 11 13 17 19 23 29 31 37])
ans =
     2     1     3     6     4     1     3     4    22    16    25

我们知道N后面的下一个素数必须是奇数，并且我们可以立即丢弃这个小素数列表中的所有奇数倍。这些模使我们可以筛选出那些小素数的倍数。如果我们使用小于200的小素数，我们可以使用这个方案立即丢弃大多数大于N的潜在素数，除了一个小列表。

更明确地说，如果我们寻找一个超过2534536543556的质数，它不能被2整除，所以我们只需要考虑超过这个值的奇数。上面的模数表明，2534536543556与2 mod 3相同，因此2534536543556+1与0 mod 3相同，这必须是2534536543556+7,2534536543556+13等。有效地，我们可以筛选出许多数字，而不需要测试它们的素性，也不需要任何试除法。

类似地，事实是

mod(2534536543556,7) = 3

告诉我们2534536543556+4与0mod7同余。当然，这个数字是偶数，所以我们可以忽略它。但是2534536543556+11是一个可以被7整除的奇数，2534536543556+25也是如此。同样，我们可以清楚地将这些数字排除在外(因为它们可以被7整除)，因此不是素数。

只使用最多37个素数的小列表，我们可以排除紧跟在起点2534536543556之后的大多数数字，只有几个除外：

{2534536543573 , 2534536543579 , 2534536543597}

在这些数字中，它们是质数吗？

2534536543573 = 1430239 * 1772107
2534536543579 = 99833 * 25387763

我已经尽力提供了列表中前两个数字的素数分解。注意它们是复合的，但主因子很大。当然，这是有道理的，因为我们已经确保了剩余的数字都不能有小的素数因子。我们的短列表中的第三个(2534536543597)实际上是N之外的第一个素数。我描述的筛选方案往往会导致数字要么是素数，要么是由通常较大的素数因子组成。因此，在找到下一个素数之前，我们实际上只需要对几个数字应用显式质数测试。

类似的方案很快就会产生超过N= 1000000000000000000000000000的下一个素数，如100000000000000000000000000103。