为何将计算量减半后，素数程序运行时间仅获小幅提升？

这是个很典型的优化误区——你优化的是待检查数的数量，但原程序的时间瓶颈其实在每个数的因数检查过程，而非遍历的次数。咱们拆解来看：

1. 原算法的核心耗时点 #

你的初始思路是遍历奇数+试除到sqrt(i)，这个试除过程才是真正吃时间的地方。比如对于i=1e6附近的数，sqrt(i)≈1000，意味着每个数要做近500次奇因数检查（因为只看奇数）。就算你把待检查数砍掉一半，每个数的检查成本还是没变，总时间自然只会小幅下降——相当于你少做了一半的“高成本任务”，但单个任务的耗时没减少，整体收益当然有限。

2. 额外的判断开销抵消了部分收益 #

为了剔除3、5、7的倍数，你需要给每个候选数额外增加三次取模判断（i%3 == 0、i%5 == 0、i%7 == 0）。这部分操作虽然简单，但架不住遍历的基数大，会额外消耗一些CPU周期，进一步抵消了减少待检查数带来的时间节省。

3. 真正有效的优化方向 #

如果想大幅提升速度，得从降低单个素数检查的成本入手，比如：

• 埃拉托斯特尼筛法（Sieve of Eratosthenes）：这是素数统计的经典高效算法，时间复杂度是O(n log log n)。思路是创建一个布尔数组标记素数，从2开始，把每个素数的所有倍数标记为非素数，最后直接统计未被标记的数。对于1e6的规模，这个算法跑起来几乎是瞬间的，远快于你的试除法。
• 优化试除的因数范围：不要遍历所有奇数，而是只遍历已经找到的素数来试除。比如你先找到3、5、7这些素数，之后检查更大的数时，只用这些素数去试除到sqrt(i)，这样试除的次数会比遍历所有奇数少很多。
• 提前终止试除：一旦找到一个因数，立刻判定该数不是素数，停止后续检查（如果还没做的话，这也是个关键优化）。

举个直观的对比：用埃氏筛处理1e6的素数，在普通PC上可能只需要几毫秒，而你的试除法要一分多钟——这就是算法复杂度带来的差距。

内容的提问来源于stack exchange，提问作者Ovi