求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
解题思路
- 质因数的遍历范围是2到sqrt（n），这样时间复杂度大大降低；
- 因为是从小到大的顺序找的所以肯定都是质因数（无需再用函数判断），否则在之前就已经在while循环里被除掉了。小于它的所有数已经被除掉了，所以如果可以整除就一定是质数
- 当每找到一个质因数以后，立刻整除掉它，紧接着增加质因数个数。
- 如果遍历到了sqrt（n）时还是大于1，则肯定还剩最后一个质因数。比如计算120的质因数个数时，最后计算到n=5，2<sqrt(5)<3，而之前i=3（因为120=22235），所以i循环已结束，最后剩下的那个质因数就是5。
#include<stdio.h>
int main(){
int n;
int count=0;
scanf("%d",&n);
for(int i=2;i<=sqrt(n);i++){
while(n%i==0){
count++;
n/=i;
}
}
if(n!=1) count++;//此时n必为大于sqrt(n)的质数
printf("%d\n",count);
网友评论