我刚刚证明了埃拉托斯特尼筛法的效率低于试除法吗？

我试图比较两种算法的运行时速度：一个用于打印素数（10,000 个数字）的强力 C 程序，以及一个埃拉托斯特尼筛法 C 程序（也是 10,000 个素数）。

我测量的筛子算法的运行时间是：0.744 秒

我测量的暴力算法的运行时间是：0.262 秒

然而，我被告知埃拉托色尼筛法比暴力法更有效，所以我认为它可以运行faster。所以要么我错了，要么我的程序有缺陷（我对此表示怀疑）。

因此，我的问题是：既然我得到了与我预期相反的结果，这是否证明埃拉托斯特尼筛确实是less与试除法相比，算法在速度方面是否高效？

我不确定它是否有任何相关性，但我正在使用 Dev C++ 编译器和 Windows 7。

TL;DR:仅比较一种输入大小的代码变体的速度是没有意义的；比较经验增长阶数真实反映算法的代码的性质，并且对于输入大小的相同测试范围，在不同的测试平台上将保持一致。比较绝对速度值仅对于表现出相同渐近或至少局部增长行为的代码变体有意义。

仅在一种输入大小下测量两种实现的速度是不够的。通常需要多个数据点来评估运行时间经验增长阶数 http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth我们的代码（因为代码可以使用不同的输入大小运行）。它是基于输入大小比率的运行时间比率的对数。

所以即使在某些输入code_1 runs 10比code_2，但是它的运行时间doubles输入大小每次加倍，而对于code_2它只会增长1.1x， 很快code_2会变得比code_1.

所以衡量一个算法效率的真正标准是它的运行时复杂度 http://en.wikipedia.org/wiki/Time_complexity（以及其空间的复杂性，即内存要求）。当我们凭经验测量它时，我们只测量手头的特定代码（在特定的输入大小范围内），而不是测量算法本身，即它的理想实现。

特别地，试除法的理论复杂度为O(n^1.5 / (log n)^0.5), in n产生的素数，通常被视为~ n^1.40..1.45经验增长顺序（但可以是~n^1.3最初，对于较小的输入大小）。对于埃拉托斯特尼筛来说是O(n log n log (log n))，通常被视为~ n^1.1..1.2。但肯定存在试除法和埃拉托色尼筛的次优实现，其运行速度为~n^2.0更糟糕的是。

So no，这证明不了什么。一个数据点毫无意义，至少三个需要获得“大局”，即能够predict可以肯定的是，更大的输入大小所需的运行时间/空间。

预言已知的确定性是科学的方法 http://en.wikipedia.org/wiki/Scientific_method就是这样。

顺便说一句，你的运行时间很长。 10,000 个素数的计算应该几乎是瞬时的，对于在快速机器上运行的 C 程序来说，远小于 1/100 秒。也许您也在测量打印时间。不。 :)