题目描述
求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。
输入描述:
可能有多组测试数据,每组测试数据的输入是一个正整数N,(1<N<10^9)。
输出描述:
对于每组数据,输出N的质因数的个数。
示例1
输入
120
输出
5
/* 程序设计思想: 关键点:1.用sqrt()对N进行处理,可以极大减少复杂度,若是到方根N仍大于1小于2,则必还有且只还有1个质因数。 2.每次瞬间整除可帮助减少遍历范围。 3.为什么不用判断j是否为质数? 因为任何一个合数都能被一个比它小的质数整除。所以当我们用小质数去分解这个给定的数时,我们已经把他的合数因子分解了。 或者从反面去说,如果出现了一个合数a能整除这个数M,那显然在j =a之前应该有一个质数p < a 能把a整除, 而之前反复地用M去除以p直到p不能再整除M 程序才往下执行,那怎么会后来又出现了M中一个合数因子a能被p整除呢? 这显然矛盾了。从而可以推出,程序中能整除M的数都是质数。 */ #include <iostream> #include <cmath> using namespace std; int main(){ long N=100; while(cin>>N) { long count=0; for(long j=2;j<=sqrt(N);j++){ while(N%j==0){ //j必为质数 N=N/j; count++; } if(N<=1) break; } if(N>1) count++; cout<<count<<endl; } return 0; }