[請益] 判斷完全數 - 改善效率 (已解決)
※ [本文轉錄自 Prob_Solve 看板 #1E6menaK ]
作者: 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(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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.73.222
→
07/11 22:49, , 1F
07/11 22:49, 1F
→
07/11 23:00, , 2F
07/11 23:00, 2F
數字大不大我倒真不確定, 但我比較好奇的是，這個表要怎麼建？
能否指教一二？
→
07/11 23:03, , 3F
07/11 23:03, 3F
→
07/11 23:04, , 4F
07/11 23:04, 4F
→
07/11 23:06, , 5F
07/11 23:06, 5F
※ 編輯: tropical72 來自: 180.177.73.222 (07/11 23:08)
→
07/11 23:27, , 6F
07/11 23:27, 6F
→
07/11 23:27, , 7F
07/11 23:27, 7F
→
07/11 23:30, , 8F
07/11 23:30, 8F
→
07/12 00:01, , 9F
07/12 00:01, 9F
→
07/12 00:06, , 10F
07/12 00:06, 10F
→
07/12 00:07, , 11F
07/12 00:07, 11F
→
07/12 00:08, , 12F
07/12 00:08, 12F
→
07/12 00:26, , 13F
07/12 00:26, 13F
→
07/12 00:27, , 14F
07/12 00:27, 14F
→
07/12 00:35, , 15F
07/12 00:35, 15F
→
07/12 00:39, , 16F
07/12 00:39, 16F
→
07/12 09:00, , 17F
07/12 09:00, 17F
→
07/12 09:01, , 18F
07/12 09:01, 18F
→
07/12 09:02, , 19F
07/12 09:02, 19F
→
07/12 14:15, , 20F
07/12 14:15, 20F
→
07/12 14:34, , 21F
07/12 14:34, 21F
→
07/12 14:47, , 22F
07/12 14:47, 22F
→
07/12 14:55, , 23F
07/12 14:55, 23F
→
07/12 14:59, , 24F
07/12 14:59, 24F