抱歉，我對於我的程式這些TLE實在沒有頭緒，已經盡量使用最快的方法了，在之前有爬過文，我的演算法也是用找到可除掉的數就除掉原數，再將原數繼續找到方法，不知道是哪裡出了問題？麻煩高人解答！！
程式碼：
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
bool IsPrime( long long int num ) {
// num代表代測數
long long int sqrtnum = (long long int)sqrt( (double)num ) ;
// 此時要開始檢察sqrt到num是不是原num的因數
if ( sqrtnum == 1 && num != 1 ) // 2、3都是質數
return true ;
else if ( num == 1 )
return false ;
else {
for ( int i = sqrtnum ; i > 1 ; i -- )
if ( num%i == 0 ) // 代表小於 sqrtnum的數有數字是num的因數
return false ;
return true ;
} // else
} // IsPrime()
int PrimeSeries( int num ) {
// 傳入一個序列數，傳出這個序列數的質數
// 如1是2，2是3，3是5，4是7
int theprime = 2 ;
for ( int i = 1 ; i < num ; i ++ ) {
theprime ++ ;
while ( ! IsPrime( theprime ) ) { // 找到theprime真真正正是質數為止。
theprime ++ ;
} // while
} // for
return theprime ;
} // PrimeSeries()
int main() {
int reduce = 0, i = 1, reducenums = 1 ; // 預備做質因數分解
// 其實reduce是垃圾分解的意思(囧)
bool first = true ;
while ( EOF!= scanf( "%d", &reduce ) ) {
first = true ;
while ( reduce != 1 ) {
if ( ! first )
printf( " * " ) ;
// 先找最小的質數分解他
i = 1 ;
for ( ; reduce % PrimeSeries(i) != 0 ; i ++ ) ;
printf( "%d",PrimeSeries( i ) ) ; // 找到了，印出來
reduce /= PrimeSeries( i ) ;
reducenums = 1 ; // 可以被除的次數 // 已經檢查過一次了，所以初始值是1
// 如果可以繼續用同一個數分解的話就繼續分解
if ( reduce % PrimeSeries( i ) == 0 ) {
printf( "^" ) ;
while ( reduce % PrimeSeries(i) == 0 ) {
reduce /= PrimeSeries( i ) ;
reducenums ++ ;
} // while
printf( "%d", reducenums ) ;
} // if
first = false ;
} // while
printf( "\n" ) ;
} // while
return 0 ;
} // main()
謝謝各位高手！
改用cin系列的程式碼：(本來想說會不會是EOF的問題)
# include <iostream>
# include <stdlib.h>
# include <math.h>
using namespace std ;
bool IsPrime( int num ) {
// num代表待測數
int sqrtnum = (int)sqrt( (double)num ) ;
// 此時要開始檢察sqrt到num是不是原num的因數
if ( sqrtnum == 1 && num != 1 ) // 2、3都是質數
return true ;
else if ( num == 1 )
return false ;
else {
for ( int i = sqrtnum ; i > 1 ; i -- )
if ( num%i == 0 ) // 代表小於 sqrtnum的數有數字是num的因數
return false ;
return true ;
} // else
} // IsPrime()
int PrimeSeries( int num ) {
// 傳入一個序列數，傳出這個序列數的質數
// 如1是2，2是3，3是5，4是7，5是11
int theprime = 2 ;
for ( int i = 1 ; i < num ; i ++ ) {
theprime ++ ;
while ( ! IsPrime( theprime ) ) { // 找到theprime真真正正是質數為止。
theprime ++ ;
} // while
} // for
return theprime ;
} // PrimeSeries()
int main() {
int reduce = 0, i = 1, reducenums = 1 ; // 預備做質因數分解
// 其實reduce是垃圾分解的意思(囧)
bool first = true ;
while ( cin >> reduce ) {
first = true ;
while ( reduce != 1 ) {
if ( ! first )
cout << " * " ;
// 先找最小的質數分解他
i = 1 ;
for ( ; reduce % PrimeSeries(i) != 0 ; i ++ ) ;
cout << PrimeSeries( i ) ; // 找到了，印出來
reduce /= PrimeSeries( i ) ;
reducenums = 1 ; // 可以被除的次數 // 已經檢查過一次了，所以初始值是1
// 如果可以繼續用同一個數分解的話就繼續
if ( reduce % PrimeSeries( i ) == 0 ) {
cout << "^" ;
while ( reduce % PrimeSeries(i) == 0 ) {
reduce /= PrimeSeries( i ) ;
reducenums ++ ;
} // while
cout << reducenums ;
} // if
first = false ;
} // while
cout << endl ;
} // while
return 0 ;
} // main()
/*
還是TLE...請問我的演算法有可以改進的空間嗎？
我的演算法：
1.找到第一個可以把待測數字除掉的數，然後除掉，並接著除，看可以除掉幾次
2.接著找，直到待測數字被除到1
我知道我這個演算法有一個問題就是如果有待測數有很大的質因數(如155114)，就要找很久。
可是我不知道如何解決這個問題。
有好心的高手大人，可以幫我解決這個問題嗎？或換個更好的演算法給我？
*/