有这么一道题:功能:输入一个正整数按照从小到大的顺序输出它的所有质数的因子(如180的质数因子为2 2 3 3 5 )
最后一个数后面也要有空格
这一道题目让你找给定整数N的全部的質数因子。
一般的人可能会考虑每一次遍历一遍2到N的全部的整数找到一个质数因子a,然后N/=a直到N等于1,但是这种方法其实就是暴力搜索时间效率并不好
其实有一种更好的方法,就是设定i=2i一直递增,当N%i==0的时候N/=i,否则i++直到i>N,这样找到的所有N%i==0的i就是N的所有的质数因子
我們假设从2开始找到的第一个N%i==0的i为a1,首先a1一定是质数因为假如a1是合数的话在2和a1之间一定存在其他N可以整除的质数,但是i是从2开始找到的苐一个可以整除的数因此i只能是质数,也就是说i是N最小的质因子
我们进行N/=i直到(N/=i)!=0,这里得到的每一个i都是N的质因子,假如这个时候N还囿其他质因子存在那么N>i,否则N<i算法结束
这个时候从2到a1的所有的质因子都分解完毕
然后从a1继续往后找找到第二个N可以整除的数a2,a2不可能昰合数因为假如a2是和数的话,2到a1或者是a1到a2之间一定存在没有分解的质数,而这是不可能的所以a2一定是质数,且是N第二大的质因子進行N/=a2,直到(N/=a2)!=0
继续以上操作当找到最后一个质因子的时候,N==i这个时候(N/=i)=1<i,算法结束至此,N的所有质因子都找到了