完全数
完全数というのは、自分自身以外の約数の総和が自分自身に等しくなる自然数の事です。例えば6の約数は1, 2, 3でその和は6となりますので完全数です。まずは、この定義通りにプログラムを作り完全数を調べだしてみます。
#include <stdio.h>
#include <stdlib.h>
int main( int ac, char *av[] )
{
long long n, min_n, max_n, sum, i;
/* コマンドラインから探索範囲を決定する */
if( ac < 3 ) {
fprintf( stderr, "usage : perfect min_n max_n\n" );
return( 1 );
}
min_n = strtoll( av[1], NULL, 10 );
max_n = strtoll( av[2], NULL, 10 );
if( min_n < 1 || max_n < 1 ) {
fprintf( stderr, "bad parameter\n" );
return( 1 );
}
/* 探索範囲の数を調べる */
for( n = min_n; n <= max_n; n++ ) {
/* 約数の和を求める */
sum = 0;
for( i = 1; i <= n / i; i++ ) {
if( n % i == 0 ) {
sum += i;
if( n / i != i && i != 1 )
sum += ( n / i );
}
}
/* 約数の和が自身に等しければ完全数である */
if( sum == n )
printf( "%lld\n", n );
}
return( 0 );
}
まず10000以下の範囲で調べてみた所、見つかった完全数は6、28、496、8128でした。このプログラムは素数の場合と同様、広い範囲の数を探そうとすると膨大な時間が掛かってしまうという欠点があります。
(2012/2/12追記)
Athlon 64 X2で実行したところ、10万以下の値について探索するのに78秒掛かりました。
(2020/4/25追記)
ソースコードを少し整理しました。
(2026/3/9追記)
int を long long に変更するとともに、ソースコードを少し整理しました。
(2026/3/27追記)
高速化のため、√n以下の数字までしか検証しないように修正しました。
完全数の場合は後述の約数和配列を用いることで効率的に求められることからあまり意味がないのですが、同様に約数和配列を用いる友愛数や婚約数では大きな意味を持ちます。同じような処理は同じように修正しておく方がいいということで、こちらも修正しました。
約数和配列
完全数を単純な方法で探し出そうとすると、とてつもなく計算コストが掛かります。そこで、効率の良い方法として、エラトステネスのふるいをヒントに次のようなものを考えました。
まず配列を用意します。次に2以上の整数の倍数を求め、その値の配列に元の整数を加えます。整数を配列要素数まで繰り返せば、各配列には添え字の約数の総和が入っていることになります。添え字と約数の和が等しければ、その値は完全数となります。
素数を求める時と同様、この配列を繰り返し使うことによって、大きな範囲を探せるようにしました。
#include <stdio.h>
#include <stdlib.h>
#define DIVISORSUMLIST_SIZE_MAX (100000000)
long long divisorsumlist[DIVISORSUMLIST_SIZE_MAX];
int main( int ac, char *av[] )
{
long long divisorsumlistsize, i, j, base, min_n, max_n;
/* コマンドラインから探索範囲を決定する */
if( ac < 3 ) {
fprintf( stderr, "usage : perfectarray min_n max_n\n" );
return( 1 );
}
min_n = strtoll( av[1], NULL, 10 );
max_n = strtoll( av[2], NULL, 10 );
if( min_n < 1 || max_n < 1 ) {
fprintf( stderr, "bad parameter\n" );
return( 1 );
}
/* DIVISORSUMLIST_SIZE_MAX分ごとの整数区間を調べる */
for( base = min_n; base <= max_n; base += DIVISORSUMLIST_SIZE_MAX ) {
/* 整数区間配列の大きさを決める */
if( max_n - base + 1 > DIVISORSUMLIST_SIZE_MAX )
divisorsumlistsize = DIVISORSUMLIST_SIZE_MAX;
else
divisorsumlistsize = max_n - base + 1;
/* 配列を初期化する */
for( i = 0; i < divisorsumlistsize; i++ )
divisorsumlist[i] = 0;
/* 約数の和を求める */
for( i = 1; i <= ( base + divisorsumlistsize ) / 2; i++ ) {
j = ( base + i - 1 ) / i * i;
if( j < i * 2 )
j = i * 2;
for( ; j < base + divisorsumlistsize; j += i )
divisorsumlist[j - base] += i;
}
/* 約数の和とその数自身が等しければ完全数である */
for( i = 0; i < divisorsumlistsize; i++ ) {
if( divisorsumlist[i] == base + i )
printf( "%lld\n", base + i );
}
}
return( 0 );
}
このプログラムを使用して10億以下の値について探索した結果、更に33550336が完全数であることがさらに判明しました。ここまでの計算時間は約1日ですから、単純な方法に比べて随分と計算効率が良いことが分かります。
(2012/2/12追記)
Athlon 64 X2 5600+(2.9GHz)で実行したところ、10万以下の値について探索するのに0.01秒、10億以下の探索は1時間半ほどで終了しました。やっぱり今時のCPUは速いですね。
(2012/2/16追記)
メモリが潤沢に使用できるようになったので配列のサイズを1億に増やしました。これにより10億以下の値についての探索は約15分で終了するようになりました。
(2020/4/9追記)
GMPを使用するように書き換えてより広い範囲を探索できるようにした版を用いて、100億以下の範囲で探索したところ、8589869056が見つかりました。
(2020/4/25追記)
ソースコードを少し整理しました。
(2026/3/9追記)
GMP を long long に変更するとともに、ソースコードを少し整理しました。
完全数の一覧
これまでにこのページで見つけた完全数の一覧を載せておきます。
世の中では現時点で51個の完全数が見つかっているそうですが、このページでは自力で求めたものだけを掲載することにしていますので、今のところ下記のみとなります。
- 6
- 28
- 496
- 8128
- 33550336
- 8589869056
(2026/1/28追記)
2024年11月に完全数と関係のあるメルセンヌ素数が発見されており、既知の完全数も52個となりました。