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

Question

一位同事刚刚告诉我，由于与散列相关的神秘原因，C# 字典集合会按素数调整大小。我的直接问题是，“它如何知道下一个质数是什么？他们是在讲述一个巨大的表还是动态计算？这是一个可怕的插入上的非确定性运行时导致调整大小”

所以我的问题是，给定 N，这是一个质数，计算下一个质数的最有效方法是什么？

Answer 1

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

对于 p=10,000，这是 O(921) 次操作。请记住，我们将在每次 O(ln(p)) 插入(粗略地说)时执行一次此操作，这完全在大多数现代硬件上以毫秒为单位的大多数问题的限制范围内。