c# - 为什么在.Net中HashHelpers.IsPrime是这样实现的呢？

Question

关注 .NET System.Collections.Generic.Dictionary<T,T>实现我找到了一个方法 HashHelpers.IsPrime(n)检查数字是否为素数。我有点困惑，为什么他们使用非常简单的优化技术只测试从 3 开始的奇数。

(来自源代码)

int limit = (int)Math.Sqrt (candidate);
for (int divisor = 3; divisor <= limit; divisor+=2)
{
     if ((candidate % divisor) == 0)
          return false;
     }
return true;

因此，他们将两次入住的次数从 3 次减少到上限。但更优化的是根据 Wikipedia 测试数字 6*k-1,6*k+1减少 3 次测试。而且我认为素数测试还有更优、更快的解决方案。

我特别了解 Dictionary<T,T>实现它并不是那么重要，因为它只在巨大的字典中被调用，并且在极少数情况下会在调整大小时被调用。但总的来说，它是一个框架，非常受知名公司欢迎。也许存在一些逻辑或者我在这里没有看到什么？谢谢。

Answer 1

I think there's even more optimal and faster solutions for primality test.

是的。

Maybe some logic exists or I don't see something here?

没有。您已经准确地总结了情况。

你问:

Why in .Net HashHelpers.IsPrime is implemented in a non-optimal way?

然后你回答你自己的问题:

I understand that in particular Dictionary<T,T> implementation it's not so important because it is called only for huge dictionaries and in pretty rare cases while resizing.

所以您知道问题的答案。 它没有优化，因为根据定义，足够快就是足够快，并且给定的算法也足够快。

如果你想让它更快，嘿，它是开源的。去实现你更喜欢的算法，并提交你精心设计的、准确和精确的经验性能测试的详细结果，这些测试清楚地表明对广泛使用的基础功能进行不必要的更改 在不重要且罕见的情况下，您的卓越性能算法证明了这一点。

如果这听起来像是几乎没有任何好处的大量工作，那么您知道问题的答案了。成本高但 yield 小的工作排在优先级列表的底部。