题目1137: 质因数的个数
题目描述求正整数N(N>1)的质因数的个数。
相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
输入
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。
输出
对于每组数据，输出N的质因数的个数。
样例输入
120
200
样例输出
5
5
提示 [+]
*** 提示已隐藏，点击上方 [+] 可显示 ***
来源
2007年清华大学计算机研究生机试真题
【思路】：
[cpp]
/*********************************
* 日期：2013-3-20
* 作者：SJF0115
* 题号: 题目1137: 质因数的个数
* 来源：http://ac.jobdu.com/problem.php?pid=1137
* 结果：AC
* 来源：2007年清华大学计算机研究生机试真题
* 总结：
**********************************/
#include<stdio.h>
#include<string.h>
#define MAXSIZE 100001
int 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<stdio.h>
#include<string.h>
#define MAXSIZE 100001
int 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;
}
这个算法可以保存了各个质因数
[cpp]
/*********************************
* 日期：2013-3-20
* 作者：SJF0115
* 题号: 题目1137: 质因数的个数
* 来源：http://ac.jobdu.com/problem.php?pid=1137
* 结果：AC
* 来源：2007年清华大学计算机研究生机试真题
* 总结：
**********************************/
#include<stdio.h>
#include<string.h>
#define MAXSIZE 100001
int Mark[MAXSIZE];
int prime[MAXSIZE];
//判断是否是一个素数 Mark 标记数组 index 素数个数
int IsPrime(){
int index = 0;
memset(Mark,0,sizeof(Mark));
for(int i = 2; i < MAXSIZE; i++)
{
补充：软件开发 , C++ ,
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊