数学c上2，下4怎么计算

【一、软件的好和坏是感觉出来的吗？】
经常有人说苹果的系统“好”，或者有些软件非常好，但为什么好，没有一个非常明确标准，甚至只是一种使用的感觉而已。
然而这种感觉并不是虚幻的，站在编程角度，算法的实现和算法的优化，可以作为两个概念，算法的实现容易看到成果，所以很多人只关注算法的实现，而算法的优化，需要付出很多精力，却不一定被用户明显觉察到。
有些公司团队，觉得能实现某个算法就很不容易了，哪有时间精力再去优化算法，开发周期还在催着，哪有心思再去尝试更好的算法？于是，软件和软件之间，系统和系统之间就拉开了差距。

【二、编程算法需要数学素养吗？】
开发工作中越来越感觉到数学的重要，数学能力，数学思维，数学素养都会影响到开发的质量。
接下来我们用一个小的编程案例，来展示一下算法实现与算法优化，展示一下数学基础素养的重要性。
案例为求质数数量，质数也叫素数，只能被1和自身整除的自然数，1既不是质素也不是合数，2是最小质数，也是唯一的偶数质数。
题目1：求10（十）以内有多少个质数？
题目2：求100（百）以内有多少个质数？
题目3：求1000（千）以内有多少个质数？
题目4：求10000000（千万）以内有多少个质数？
题目5：求100000000（一亿）以内有多少个质数？
题目6：求1000000000（十亿）以内有多少个质数？

解答题目1，直接枚举就可以：2、3、5、7共计4个质数。
解答题目2，仍可以沉下心来继续枚举，也可以写几行代码编程实现，这个时候，两种方法可能实现的时间可能是不相上下的，答案是25个。
解答题目3，想都不用想，枚举计算正常人几乎是不可能完成的，必须编程实现，这时候计算机的优势和价值就体现出来了。
以下编程测试在一台普通笔记本进行，配置截图如下：

接下来用C++进行编程示例，只要按照质数定义逐个测试就行，毕竟计算机计算速度是很快。
要判断 x 是否为质数，就从2一直尝试到 x-1，全都不能整除，则x为质数。实现代码如下：

运行结果：

好像很成功，0.06秒就计算出结果

解答题目4，按说有了解答题目3的程序，只要把m=1000，改为m=10000000 ,就可以了。但是，问题出现了，屏幕面前等了一个小时了也没有出现结果，计算机还在不停的计算中……预计需要几个小时吧。

怎么办？电脑硬件配置低？换超级计算机？好像还没有必要吧，这个时候回到题目本身研究（纯数学研究），就可以发现规律，第二个for循环，其实不用计算到t-1；只要计算到t的平方根就可以了。这就是数学思维，这就是算法优化。我们看一下优化后的结果：

用时7.229秒，效率相差成千上万倍！

解答题目5，同理，算法如何继续优化？
再次回到数学研究上，我们发现凡是能被2整除的，4、6、8等2的倍数就不用再计算了，同理能被3整除的，3的倍数的其他数就不用计算了；以此类推，利用已经算出的质数，只计算能否被已经计算出的质数整除即可；这样可以减少计算量：当然这个时候要存储已经计算出的质数，如果用数组，需要占用大量内存。最多可以计算百万级别。

如果用链表，这就用到了复杂一些的数据结构，有些编程书籍经常说：
程序=数据结构+算法
改良后的程序可以运算一个亿级别。

用时30.08秒，计算出了1亿内质数

解答题目6，计算十亿以内的质数，用上一个方案计算，就很焦急了。怎么办？
还是要回到寻找数学规律上，有一种办法叫筛选法（如下图）：2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数……
　　上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。

代码及运行结果如下：

用时38.64秒，完成十亿级计算
这种算法完全避开了质数的直接定义，计算效率反而大大提升，这才是不走寻常路，神操作，神算法！
这就是最佳方案了吗？肯定不是的，没有最好，只有更好。只是我们案例到此一段落。

【四、对比：运算时间】
用题目4（求1000万内质数数量）作为对比，看不同算法的时间差异。

方案一：质数定义算法，用时13240秒，约220.67分钟，约3.68小时

方案二：计算到平方根，用时7.453秒

方案三：利用已经计算出的质数，用时1.527秒

方案四：筛选法，用时0.4024秒。

用时对比：13240:7.453:1.527:0.4024，
化简为：32000:20:4:1，也就是方案一和方案四效率相差3万倍以上；如果计算更大的数，这个差别将更大。
由此可见：不同的算法，有着几万倍的运行效率差别。

【五、对比：一分钟内对比数量级】
如果以60秒以内作为可以等待结果的时间
方案一可以做十万级计算；
方案二可以做千万级计算，
方案三可以做一亿级计算；
方案四可以做十亿级计算。
由此可见：不同的算法，有着不同数量级的计算。

【六、结论及延伸】

复杂的算法还是需要数学素养的，但不是说数学不好就不能编程，毕竟大量的编程不涉及高深的数学算法。
本文真正的结论是：不能仅仅满足于算法的实现，应该养成好的编程素养：算法优化，追求更佳！

您可能感兴趣问答

Collapsible

热门标签

热点问答