[請益] 判斷完全數 - 改善效率 (已解決)

[tropical72 (藍影)]

※ [本文轉錄自 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
→ firejox:可能是ceil的緣故...
→ firejox:假如數字不大我就會考慮建表XD
數字大不大我倒真不確定, 但我比較好奇的是，這個表要怎麼建？
能否指教一二？
→ firejox:就像篩法方式去建表呀...
→ tropical72:我懂你意思了, 謝謝.
→ tropical72:重點是那個 if(end*end==x),已AC,謝謝 firejox. *^_^*
※ 編輯: tropical72      來自: 180.177.73.222       (07/11 23:08)
→ firejox:還有一招是先質因數分解~~
→ Favonia:那個... 數字太大時 sqrt 會不夠「準」xD 不過大概無所謂
→ rmbrick:我有個作法是直接質因數分解  這在數字大的時候快很多
→ tropical72:我好奇質因數實際寫法.120=2*2*2*2*3*5,因數 ?
→ CindyLinz:120因數: 1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120
→ firejox:只需質因數和次方數即可算
→ firejox:(2^4+2^3+..+1)(3+1)(5+1) 是全部因數和...
→ firejox:http://codepad.org/x5Pedc1C
→ tropical72:這公式還真神奇,怎麼我數學課都沒上課.謝謝firejox ^^
→ tropical72:補一下,zerojudge下,這二個方法差不多,應數字都不大.
→ firejox:看來是如此
→ angleevil:其實這是我長久以來的疑問tropica是財金系,為何會學這些
→ angleevil:最難理解的是他懂爆多的資訊底層技術東西.難道只是有心
→ angleevil:的差別嘛
→ tropical72:耶..我好像只有說過我是商科,不是財金,別誤會 ^^
→ angleevil:TAT還是比我強阿
→ tropical72:TAT ? Tourism Authority of Thailand ?泰國觀光局?
→ angleevil:不是英文,那是表情.
→ tropical72:oh, 誤會一場 XD.