题目1137: 质因数的个数
本文共 2577 字，大约阅读时间需要 8 分钟。
题目描述
求正整数N(N>1)的质因数的个数。
相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
输入
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。
输出
对于每组数据，输出N的质因数的个数。
样例输入
120 200
样例输出
5 5
提示 [+]
*** 提示已隐藏，点击上方 [+] 可显示 ***
来源
/********************************* * 日期：2013-3-20* 作者：SJF0115 * 题号: 题目1137: 质因数的个数* 来源：http://ac.jobdu.com/problem.php?pid=1137* 结果：AC * 来源：2007年清华大学计算机研究生机试真题* 总结： **********************************/ #include#include #define MAXSIZE 100001int Mark[MAXSIZE];int prime[MAXSIZE];//判断是否是一个素数 Mark 标记数组 index 素数个数int IsPrime(){ int index = 0; memset(Mark,0,sizeof(Mark)); for(int i = 2; i < MAXSIZE; i++) { //i*i > MAXSIZE if(i > 1000){ break; } //如果标记跳过 if(Mark[i] == 1){ continue; } else{ prime[index++] = i; //标记目前得到的素数的i倍为非素数 for(int j = i*i; j < MAXSIZE; j += i) { Mark[j] = 1; } } } return index;}int main (){ int a,index,count; while(scanf("%d",&a) != EOF){ count = 0; index = IsPrime(); for(int i = 0;i < index && a != 1;i++){ //如果a能整除prime[i] while(a % prime[i] == 0){ count ++; a = a / prime[i]; } } //若测试完2到100000内所有素因数都没有分解到1则a还有一个大于100000的素因数 if(a != 1){ count += 1; } printf("%d\n",count); }//while return 0;}
这个算法可以保存了各个质因数
/********************************* * 日期：2013-3-20* 作者：SJF0115 * 题号: 题目1137: 质因数的个数* 来源：http://ac.jobdu.com/problem.php?pid=1137* 结果：AC * 来源：2007年清华大学计算机研究生机试真题* 总结： **********************************/ #include#include #define MAXSIZE 100001int Mark[MAXSIZE];int prime[MAXSIZE];//判断是否是一个素数 Mark 标记数组 index 素数个数int IsPrime(){ int index = 0; memset(Mark,0,sizeof(Mark)); for(int i = 2; i < MAXSIZE; i++) { //i*i > MAXSIZE if(i > 1000){ break; } //如果标记跳过 if(Mark[i] == 1){ continue; } else{ prime[index++] = i; //标记目前得到的素数的i倍为非素数 for(int j = i*i; j < MAXSIZE; j += i) { Mark[j] = 1; } } } return index;}int main (){ int a,index,i; while(scanf("%d",&a) != EOF){ //按顺序保存分解出的质因数 int ansPrime[100]; //对应质因数的个数 int ansNum[100]; int ansIndex = 0; memset(ansNum,0,sizeof(ansNum)); index = IsPrime(); for(i = 0;i < index && a != 1;i++){ //如果a能整除prime[i] if(a % prime[i] == 0){ //存储质因数 ansPrime[ansIndex] = prime[i]; while(a % prime[i] == 0){ //统计个数 ansNum[ansIndex] ++; a = a / prime[i]; } ansIndex ++; } } //若测试完2到100000内所有素因数都没有分解到1则a还有一个大于100000的素因数 if(a != 1){ ansPrime[ansIndex] = a; ansNum[ansIndex++] = 1;//只有一个 } int count = 0; for(i = 0;i < ansIndex; i++){ count += ansNum[i]; } printf("%d\n",count); }//while return 0;}
转载地址：http://uucsi.baihongyu.com/
你可能感兴趣的文章