如何判断这两份代码的时间复杂度？ 第1页

因为写程序是要动脑子的。

这个题目的要求是“找出所有纯质数”；而纯质数本身是非常特殊的。

第一种做法事实上完全没有利用“纯质数”这个知识点，而是去硬算，硬检查每个数字是否质数。

那么，这个复杂度就是O(N)水平，其中N等于20210605.

而每次检查的代价则是O(M)，M是小于当前数字n的平方根的所有质数个数——我不清楚质数分布状况究竟如何，但根据下面的数据，可以认为素数数量和自然数数量近乎成正比，也就是O(M)->O(M/K)。在算法理论上，这等于说算法复杂度仍然是O(n)。

换句话说，你的确可以通过一定的优化降低素性检验的消耗，但从算法理论上说，并不能改变复杂度级别。

素数分布_百度百科 (baidu.com)

下表是大约107亿以内的个位为3的素数分布情况，可以看到自然数增加一倍，素数个数增加也越来越接近一倍。当自然数趋向无穷时，其应与自然数增长比率相同。

当然，你可以在这个基础上做一点小小的优化，比如跳过所有的偶数、5结尾的数字等；但每次检查的复杂度最好也就是O（M/100）这个级别了。

而第二种做法就要聪明的多：我们可以先筛选“疑似纯素数”；那么，什么是“疑似纯素数”呢？

说白了，“疑似纯素数”实际上就是小于20210605的四进制数；这个四进制数字允许使用的4个数字符号是2、3、5、7；而且，2和5结尾的数字还可以直接剔除。

仅仅8位四进制数字（还只能2开头），再加上禁止2、5结尾，那么这实际上仅仅相当于7位四进制数字，也就是4的7次方。

相比8位十进制数字（10的8次方），待搜索空间是不是一下子缩小了很多？

换句话说，过去，检查所有小于20210605的整数是否素数，待检验的数字总量大约是10^8，大于2^24；现在这么先筛一下呢？待检验数字总量降低到了4^8，等于2^16——这显然是一个极大的优化。

当然，这样一来，素性检验就没有办法优化了，因为我们并没有找出“小于当前数字n的所有素数”；但前面提到过，这个优化并不能明显降低算法复杂度（算法理论上甚至认为相同的）。

尤其是，我们可以准备一个小于20210605的平方根的数组，预先把2、3、5、7、11等素数的倍数剔除；然后使用数组中的数字做素性检验。那么，最终，哪怕单次判断的消耗也不会比筛法高多少。

事实上，针对题目条件，你真把小于20210605的平方根的所有素数剔除，反而可能是得不偿失的。因为较大素数的重复使用率可能并没有想象的高——你可以把程序写出来，统计下每个数字的使用率，然后计算一下筛掉那些靠后的数字的消耗，得不偿失的就放弃吧：这个应该也能算，但我是懒虫……

换句话说，素性检验双方基本打平（第一种做法小胜，但不足以改变战略格局）；但后一种做法直接筛掉了绝大多数“不可能是纯素数的候选数字”，这个做法是足以改变战略格局的——那么，后者大胜自然就不奇怪了。

所以说这™还是得喂到嘴里是吧？

喏，8位十进制数字时，尾数为3的素数数量低两个数量级。也就是计算消耗可以除以100（实际不足100）——注意这里仅仅统计了尾数为3的素数，尾数为7、9的都被忽略了。也就是真实消耗还得继续倍增；且越到后期，数值范围加倍后，素数增加越趋向于加倍，也就是素数会更多。

而2^24比之2^16，小了2^8，也就是计算消耗除以255（实际大于255）；且随着n的增长，符合要求的数字会更少——因为随着10进制数字位数N的增长，前者需要考察的数字量是O(10^N)，后者需要考察的数字量仅有O(4^N)。

尤其注意，前者优化的是“每次素性检验”的消耗，而后者优化的是“需要做素性检验的数字”；因此我在上文中用N和M做了个区分，也就是提到N时就是在讨论“需要考察的数字量”，而提到M时就是在讨论“一次素性检验的消耗”——你当然可以把它们都写成N，但两者是不能随随便便乘起来的，含义都不一样。