由于质数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屋！