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

[tropical72 (藍影)]

[題目]

對一個正整數 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
→ tkcn:沒仔細看，不過 x==1 的處理是錯的
→ firejox:是因為1不是質數嗎?
→ tkcn:"將它除了本身以外所有的因數"
→ tropical72:我再改過我修過的部份, 目前仍有誤 XD
※ 編輯: tropical72      來自: 180.177.73.222       (07/11 22:59)
→ firejox:x*x==end ....
→ tropical72:對不起樓上, 是我 key 錯 XD
※ 編輯: tropical72      來自: 180.177.73.222       (07/11 23:03)
※ 編輯: tropical72      來自: 180.177.73.222       (07/11 23:07)
→ tkcn:x 減掉 EPS 再做 sqrt 試試? (int)ceil(sqrt(x-EPS))
→ tropical72:謝謝tkcn,這支程式碼已 AC, 非常感謝您的指導 *^_^*