# 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)，就要找很久。
可是我不知道如何解決這個問題。
有好心的高手大人，可以幫我解決這個問題嗎？或換個更好的演算法給我？
*/
/*
還是TLE...請問我的演算法有可以改進的空間嗎？
我的演算法：
1.找到第一個可以把待測數字除掉的數，然後除掉，並接著除，看可以除掉幾次
2.接著找，直到待測數字被除到1
我知道我這個演算法有一個問題就是如果有待測數有很大的質因數(如155114)，就要找很久。
可是我不知道如何解決這個問題。
有好心的高手大人，可以幫我解決這個問題嗎？或換個更好的演算法給我？
*/
1.既然你知道判斷質數時只要做到 sqrt(num) 就行了,
那麼在求質因數分解時, 也只要求到 sqrt(num) 以下的質因數就行了,
如果不是變成1, 那剩下的部分也是一個質數....
2.你的 PrimeSeries() 呼叫太多次, 效率會變很差,
可以一開始就把質數表建好, 之後直接查表就行了....
3.事實上, 不用建質數表也行, 也不用去判斷是不是質數,
你就用 2、3、4、5、.... 一直除上去,
除到 sqrt(num) 為止, 假設你要分解的數是 66=2*3*11,
雖然有一個因數是 6, 但是因為之前已經把 2 的因數都除掉了,
所以遇到 6 時就不會整除, 自然會跳過這個數....