[請益] 判斷完全數 - 改善效率 (已解決)
看板Prob_Solve (計算數學 Problem Solving)作者tropical72 (藍影)時間13年前 (2011/07/11 22:35)推噓0(0推 0噓 8→)留言8則, 3人參與討論串1/1
[題目]
對一個正整數 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
→
07/11 22:53, , 1F
07/11 22:53, 1F
→
07/11 22:56, , 2F
07/11 22:56, 2F
→
07/11 22:58, , 3F
07/11 22:58, 3F
→
07/11 22:59, , 4F
07/11 22:59, 4F
※ 編輯: tropical72 來自: 180.177.73.222 (07/11 22:59)
→
07/11 23:02, , 5F
07/11 23:02, 5F
→
07/11 23:03, , 6F
07/11 23:03, 6F
※ 編輯: tropical72 來自: 180.177.73.222 (07/11 23:03)
※ 編輯: tropical72 來自: 180.177.73.222 (07/11 23:07)
→
07/11 23:07, , 7F
07/11 23:07, 7F
→
07/11 23:14, , 8F
07/11 23:14, 8F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
