题目1137: 质因数的个数

本文主要是介绍题目1137: 质因数的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

求正整数N(N>1)的质因数的个数。

相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。

输入

可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。

输出

对于每组数据，输出N的质因数的个数。

样例输入

120

200

样例输出

5

5

提示 [+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

来源

2007年清华大学计算机研究生机试真题

【思路】：

/********************************* 
*   日期：2013-3-20
*   作者：SJF0115 
*   题号: 题目1137: 质因数的个数
*   来源：http://ac.jobdu.com/problem.php?pid=1137
*   结果：AC 
*   来源：2007年清华大学计算机研究生机试真题
*   总结： 
**********************************/ 
#include<stdio.h>
#include<string.h>
#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 > MAXSIZEif(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);}//whilereturn 0;
}

这个算法可以保存了各个质因数

/********************************* 
*   日期：2013-3-20
*   作者：SJF0115 
*   题号: 题目1137: 质因数的个数
*   来源：http://ac.jobdu.com/problem.php?pid=1137
*   结果：AC 
*   来源：2007年清华大学计算机研究生机试真题
*   总结： 
**********************************/ 
#include<stdio.h>
#include<string.h>
#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 > MAXSIZEif(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);}//whilereturn 0;
}

这篇关于题目1137: 质因数的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！