###题目描述
题目描述
求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235，共有5个质因数。
输入描述:
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。
输出描述:
对于每组数据，输出N的质因数的个数。
示例1
输入
120
输出
5
###代码 & 分析
最直接的想法：先用素数筛法求出一定范围的素数，然后以此取模等等等：
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<iostream>
using namespace std;
int prime[10000];
int cal[10000];
int len = 0;
int n;
void getprime(){
memset(cal, 0, sizeof(cal));
for(int i=2; i<10000; i++){
if(cal[i])
continue;
prime[len++] = i;
for(int j=2; j*i<10000; j++)
cal[i*j] = 1;
}
}
int main(){
getprime();
while(cin>>n){
int cou = 0;
for(int i=0; i<len; i++){
while(n%prime[i]==0){
cou++;
n /= prime[i];
}
if(n <= 1)
break;
}
cout<<cou<<endl;
}
}
对于这道题目，也有一种更简单的方法，根本不用求解素数，因为从2开始取模，除2其实相当于把2的倍数的因数都去掉了，换句话说，如果存在一个之后的合数因数，那么它本身的因子一定在之前就会呗去掉：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<memory.h>
#include<iostream>
using namespace std;
int main(){
long int n;
while(cin>>n){
int sum=0;
for(long int i=2; i<sqrt(n); i++){
while(n%i==0){
sum++;
n/=i;
}
if(n<=1)
break;
}
cout<<sum+1<<endl;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116808.html
