C言語で約数とか完全数とかを求めるプログラムを書いてみた

C言語で約数とか完全数とかを求めるプログラムを書いてみた

「博士の愛した数式」という本を久しぶりに読んでみた。
その中で、主人公と博士が話すシーンがある。
主人公が「28の約数を足すと、28になるんです」と言い、その後博士が完全数や過剰数、不足数について話すシーンである。

完全数、過剰数、不足数について

その数字が持つ約数を足したとき、解がその数字になる数のこと。

28 = 1 + 2 + 4 + 7 + 14

小説内では、下記のようなことが述べられていた。

• 一番小さい完全数は6
• 28の次は496、その次は8128、その次は33550336、その次は8589869056
• 約数の和がその約数を持つ数字より大きいのが過剰数、小さいのが不足数
• 1だけ小さい不足数は存在するが、1だけ大きい過剰数は存在しない(まだ発見されていない)
• 18 は 1 + 2 + 3 + 6 + 9 = 21 で過剰数
• 14 は 1 + 2 + 7 = 10 で不足数

書いてみた

流石に桁数が多いと処理に時間がかかるので、今回は10000までの数で実装した。
C言語にした理由は特にない。
あと久しぶりに、かつテキトーに書いたので汚い部分もある…。

多分小説内にある数字と結果は一致したので合っているんじゃないかなあ…(自信ないｗ)

/* 10000までの約数を求めるプログラム */
#include <stdio.h>
int main(void){
    int max_check_num = 10000;
    int i;
    int sum = 0;
    
    for(i = 1; i <= max_check_num; ++i){
        printf("%d を調査する", i);
        sum = divisor(i);
        if(i == sum){
        printf(" -> 完全数\n");
        }
        else if(i < sum)
        {
            printf(" -> 過剰数\n差:");
            printf("%d\n", sum-i);
        }
        else {
            printf(" -> 不足数\n差:");
            printf("%d\n",i-sum);
        }
    }
}

int divisor(int num){
    int i;
    int sum = 0;
    printf("\n約数:");
    for(i = 1; i <= num; ++i) {
        if(num % i == 0){
            printf("%d, ", i);
            if(i != num){
                sum += i;
            }
            /* ↑の条件だとi=1のときsumに入らないので、その場合用の条件分岐 */
            else if(i == 1)
            {
                sum = 1;
            }
        }
    }
    printf("自身を除く約数の合計:%d", sum);
    return sum;
}

ちなみに

この後博士は「完全数は連続した自然数の和で表すことができる」と言い、その計算も始めている。