題目描述
求正整數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++)
{
//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;
}
