作者tropical72 (藍影)
站內Prob_Solve
標題[請益] 判斷完全數 - 改善效率 (已解決)
時間Mon Jul 11 22:35:26 2011
[題目]
對一個正整數 N 而言，將它除了本身以外所有的因數加起來的總和為 S，
如果 S>N，則 N 為盈數，如果 S<N，則 N 為虧數，
而如果 S=N，則 N 為完全數(Perfect Number)。
[solve]
一般人可能會這麼做：
for(sum=1, i=2; i!=N; ++i)
if(N%i==0) sum+=i;
但我覺得效率很差，於是想了一下。
假設，N % i ==0 ，那一定可以表達成 i*j=N, 得到 j=N/i，
這樣下來，只要判斷到 sqrt(N) 即可，唯一要小心的是，
若 i*i = N 時，就不用再求 j , 基於此思考程式碼大致如下
int x, i, end, sum;
while(scanf("%d", &x)!=EOF){
if(x==1) {
puts("虧數");
continue;
}
sum=1, end = (int)ceil(sqrt(x));
for(i=2; i!=end; ++i)
if(x%i==0) sum+=i, sum+=(x/i);
// if(x%end==0) sum+=end;
if(end*end==x) sum+=end;
if(sum>x) puts("盈數");
else if(sum==x) puts("完全數");
else puts("虧數");
}
但拿這個去 run, 不是正確的, 想請教一下，是我的邏輯有問題，
還是我的碼有問題？ 謝謝各位。
--
YouLoveMe() ? LetItBe() : LetMeFree();
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.73.222
※ tropical72:轉錄至看板 C_and_CPP 07/11 22:45
1F：→ tkcn:沒仔細看，不過 x==1 的處理是錯的 07/11 22:53
2F：→ firejox:是因為1不是質數嗎? 07/11 22:56
3F：→ tkcn:"將它除了本身以外所有的因數" 07/11 22:58
4F：→ tropical72:我再改過我修過的部份, 目前仍有誤 XD 07/11 22:59
※ 編輯: tropical72 來自: 180.177.73.222 (07/11 22:59)
5F：→ firejox:x*x==end .... 07/11 23:02
6F：→ tropical72:對不起樓上, 是我 key 錯 XD 07/11 23:03
※ 編輯: tropical72 來自: 180.177.73.222 (07/11 23:03)
※ 編輯: tropical72 來自: 180.177.73.222 (07/11 23:07)
7F：→ tkcn:x 減掉 EPS 再做 sqrt 試試? (int)ceil(sqrt(x-EPS)) 07/11 23:07
8F：→ tropical72:謝謝tkcn,這支程式碼已 AC, 非常感謝您的指導 *^_^* 07/11 23:14