高校问答杨凌水上运动中心 酒店:在C语言中求素数时,为何只需要出从2 到 根号N 啊?
来源：百度文库 编辑：高校问答 时间：2024/05/09 19:16:48
这么想吧：一个数N，它是根号N的平方，那么如果它有其他约数的话，假设为A，B（约数肯定要成对出现的）必然有一个大于根号N，另一个小于根号N（显然如果都大于根号N，那相乘结果会大于N；反之会小于N），所以在找的时候，只需找到根号N即可，大于根号N的那些肯定跟小于N的成对匹配，如果小于根号N的约数都没有，显然也没有大于根号N的数与它匹配了
这样可以减小时间复杂度
如果一个数算到根号N都没有约数
那么以后就没有约数了
是数学思想
根号N^2就等于N，就是说超过根号N其实就算回来了，没意思了。
你也可以求2到N/2的!
但这样时间复杂度太大!
浪费宝贵时间!
自己掰指头算算。这已经不属于基本算法了，属程序优化部分。在科学计算中，往往计算的数据量很大，程序优化就显得十分重要了。记得我以前参加数模竞赛时，编的一个搜索算法比常规搜索效率提高3个数量级呢！