给定素数 N，计算下一个素数? [英] Given Prime Number N, Compute the Next Prime?

问题描述

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

A coworker just told me that the C# Dictionary collection resizes by prime numbers for arcane reasons relating to hashing. And my immediate question was, "how does it know what the next prime is? do they story a giant table or compute on the fly? that's a scary non-deterministic runtime on an insert causing a resize"

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

So my question is, given N, which is a prime number, what is the most efficient way to compute the next prime number?

推荐答案

连续质数之间的差距 非常小，第一个超过 100 的差距出现在素数 370261 上.这意味着即使是简单的蛮力在大多数情况下也足够快，取 O(ln(p)*sqrt(p)) 平均.

The gaps between consecutive prime numbers is known to be quite small, with the first gap of over 100 occurring for prime number 370261. That means that even a simple brute force will be fast enough in most circumstances, taking O(ln(p)*sqrt(p)) on average.

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

For p=10,000 that's O(921) operations. Bearing in mind we'll be performing this once every O(ln(p)) insertion (roughly speaking), this is well within the constraints of most problems taking on the order of a millisecond on most modern hardware.

这篇关于给定素数 N，计算下一个素数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！