题解 | #质数因子#

质数因子

http://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607

首先质数的定义是一个大于1的自然数,不能被1和本身以外的自然数整除。 思路如下: 1.输入的数字必须是大于1的 2.从2开始,尝试用这个数去整除输入的数,如果不能整除,则将除数加1后再次去除。 3.找到能除尽的除数后,将除数打印出来,然后用得到的商继续除以当前的除数,将相同的质因子 一次全部找出来并打印。如果得到的商得到的商等于当前除数,则说明质因子已经全部找出,将商 打印出来即可,如果不等于,则继续用当前除数去除当前得到的商,直到无法整除,再将除数增大,寻找 下一个能整除当前商的除数。

4.注意寻找除数时,最大除数应该是小于等于输入的自然数的平方根,否则做除法得到的商必然是小于当前除数的,这样得到的 质因子是小于前面的质因子的,而此算法是从小到大开始找质因子,必定不会出现一个更小的质因子。这一步很关键,可以大大缩减 算法的时间复杂度。

5.如果输入的数本身就是一个质数,那么直接打印这个数就可以了。

全部评论

相关推荐

07-07 11:33
江南大学 Java
已经在暑假实习了 ,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
06-17 21:57
门头沟学院 Java
白友:噗嗤,我发现有些人事就爱发这些,明明已读不回就行了,就是要恶心人
点赞 评论 收藏
分享
评论
7
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务