求约数思路整理!
前置:输入数是大于1的整数
步骤1:开平方,减少运算范围
可选:多次开平方,预防开平方后的结果是质数,若质数过大,必定能大大减少运算范围。但如果质数占比小、质数小,则是多余的时间消耗。
思考:一次开平方后结果,假如可以再开平方,最终结果可能不是单个质数,这样之前运算浪费,因为最终运算得到的第一个质数也不过是在最终目标数的开方以内。若最终数是一个质数,那么这个质数多大,而多次开方是否值得。最好的结果就是,质数大。
规律:除了2,5,其他质数都是1、3、7、9为结尾的。而这些质数的平方,也是在1,3,7,9内!至少在1、9。所以至少1、3、7、9外的结尾,寓意着这个数可能不是只有一个质数组合成。所以以此筛选,是否做多次开方。但这个的情况是为了针对此时数是质数的偶次方,如果是奇此方,意义不大。
结尾是1的2次3次方结果都是1
3的2次方结果是9,3的3次方结果是7
7的2次方结果是9,7的3次方结果是3
9的2次方结果是1,9的3次方结果是9
微妙,总之假如一次末尾判断,至少可以过滤掉其他末尾数值确定是个混合组合。
接下来就尝试一种高效的判断算法。(任务1)
步骤2:质数步进循环
探索到第一个质数后,一波运算后,下一次从质数+1开始运算。
可选:导入质数库
步骤3:是与步骤2同步生成对应约数,还是专门做一个质数组生成约数的算法。
前者嵌入步骤2,行云流水,但是可能会遇到一些要解决的问题而浪费时间。
后者之前已经做的很成熟,基本控制在纳秒级
总之先完成当前任务,再一步步优化对比之后的任务!