完全数というのは、自分自身以外の約数の総和が自分自身に等しくなる自然数の事です。例えば6の約数は1,2,3でその和は6となりますので完全数です。まずは、この定義通りにプログラムを作り完全数を調べだしてみます。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main( int ac, char *av[] )
{
unsigned long long n, min_n, max_n, sum, i;
/* コマンドラインから完全数探索範囲を決定する */
if( ac < 3 )
return;
min_n = strtouq( av[1], NULL, 10 );
if( min_n < 2 )
min_n = 2;
max_n = strtouq( av[2], NULL, 10 );
/* 探索範囲の数を調べる */
for( n = min_n; n <= max_n; n++ ) {
/* 約数の総和を求める */
sum = 0;
for( i = 1; i < n; i++ ) {
if( n % i == 0 )
sum += i;
}
/* 約数の総和が自身に等しければ完全数である */
if( sum == n )
printf( "%qu\n", n );
}
}
まず10000以下の範囲で調べてみた所、見つかった完全数は6、28、496、8128でした。このプログラムは素数の場合と同様、広い範囲の数を探そうとすると膨大な時間が掛かってしまうという欠点があります。
完全数を単純な方法で探し出そうとするととてつもなく計算コストが掛かります。そこで、効率の良い方法として、素数を効率よく探し出すエラトステネスのふるいをヒントに次のようなものを考えました。
まず配列を用意します。次に2以上の整数の倍数を求め、その値の配列に元の整数を加えます。整数を配列要素数まで繰り返せば、各配列には添え字の約数の総和が入っていることになります。添え字と約数の和が等しければ、その値は完全数となります。
素数を求める時と同様、この配列を繰り返し使うことによって、大きな範囲の完全数を探せるようにしました。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_ARRAY (1000000)
unsigned long long array[MAX_ARRAY];
void main( int ac, char *av[] )
{
unsigned long long base, arraysize, n, min_n, max_n, i;
/* コマンドラインから完全数探索範囲を決定する */
if( ac < 3 )
return;
min_n = strtouq( av[1], NULL, 10 );
if( min_n < 2 )
min_n = 2;
max_n = strtouq( av[2], NULL, 10 );
/* MAX_ARRAY分ごとの整数区間を調べる */
for( base = min_n; base < max_n; base += MAX_ARRAY ) {
/* 整数区間配列の大きさを決める */
if( max_n - base + 1 > MAX_ARRAY )
arraysize = MAX_ARRAY;
else
arraysize = max_n - base + 1;
/* 配列を初期化する */
for( i = 0; i < arraysize; i++ )
array[i] = 0;
/* 約数の和を求める */
for( n = 1; n < ( base + arraysize ) / 2; n++ ) {
if( base <= n )
i = n * 2;
else if( base % n == 0 )
i = base;
else
i = ( base / n + 1 ) * n;
for( ; i < base + arraysize; i += n )
array[i - base] += n;
}
/* 約数の和とその数自身が等しければ完全数である */
for( n = 0; n < arraysize; n++ ) {
if( array[n] == base + n )
printf( "%qu\n", base + n );
}
}
}
このプログラムを使用して10億以下の値について完全数を探索した結果、更に33550336が完全数であることがさらに判明しました。ここまでの計算時間は約1日ですから、単純な方法に比べて随分と計算効率が良いことが分かります。