C語言求完數（完全數）（詳解版）

問題描述

求某一範圍內完數的個數。

如果一個數等於它的因子之和，則稱該數為“完數”（或“完全數”)。例如，6的因子為1、2、3，而 6=1+2+3，因此6是“完數”。

問題分析

根據完數的定義，解決本題的關鍵是計算出所選取的整數i（i的取值範圍不固定）的因子（因子就是所有可以整除這個數的數），將各因子累加到變數s (記錄所有因子之和），若s等於i，則可確認i為完數，反之則不是完數。

演算法設計

對於這類求某一範圍（由於本題範圍不固定，在程式設計過程中採用鍵盤輸入的方式）內滿足條件的數時，一般釆用遍歷的方式，對給定範圍內的數值一個一個地去判斷是否滿足條件，這一過程可利用迴圈來實現。

本題的關鍵是求出選取數值i的因子，即從1到i-1範圍內能整除i的數，看某一個數j是否為i的因子，可利用語句if(i%j==0)進行判斷，求某一個數的所有因子，需要在1到i-1範圍內進行遍歷，同樣釆用迴圈實現。因此，本題從整體上看可利用兩層迴圈來實現。外層迴圈控制該數的範圍2?n；內層迴圈j控制除數的範圍為1?i，通過i對j取餘，是否等於0，找到該數的各個因子。

另外應注意每次判斷下一個選定數之前，必須將變數s的值重新置為0，程式設計過程中一定要注意變數s重新置0的位置。

程式流程圖：


下面是完整的程式碼：

#include<stdio.h>
int main()
{
    int i, j, s, n;  /*變數i控制選定數範圍，j控制除數範圍，s記錄累加因子之和*/
    printf("請輸入所選範圍上限：");
    scanf("%d", &n);  /* n的值由鍵盤輸入*/
    for( i=2; i<=n; i++ )
    {
        s=0;  /*保證每次回圈時s的初值為0*/
        for( j=1; j<i; j++ )
        {
            if(i%j == 0)  /*判斷j是否為i的因子*/
                s += j;
        }
        if(s == i)  /*判斷因子這和是否和原數相等*/
            printf("It's a perfect number:%dn", i);
    }
    return 0;
}

執行結果：
請輸入所選範圍上限：10000↙?
It's a perfect number:6
It's a perfect number:28
It's a perfect number:496
It's a perfect number:8128

知識點補充

上述程式中求某數的因子時，釆用從1到i-1範圍內進行遍歷的方法，一個數一個數地去試。這種方法可以做到沒有遺漏，但是效率不高。

對於某一整數來說，其最大因子為n/2 (若n為偶數時，若為奇數最大因子小於n/2），在n/2?n-1範圍內沒有資料可以整除此數。據此，我們可以把遍歷範圍縮小至1?n-1，這樣程式效率可以提高一倍。相應程式如下：

#include<stdio.h>>
int main()
{
    //...
    for( i=2; i<=1000; i++)
    {
        s=0;
        for( j=1; j<=n/2; j++ )
        {
            if(i%j == 0)
            s += j;
        }
    //...
    }
}