ゴールドバッハの予想を検証する

ゴールドバッハの予想を検証する

ゴールドバッハの予想とは「全ての偶数の合成数は、2個の素数の和で表すことができる」というものです。コラッツの予想と同じく、予想ですからまだ証明はされていません。

偶数の合成数ですから、2は含まれず、4以上の偶数が対象になります。4は2と2の和で表される事は簡単に分かります。偶数の素数は2だけですから、4以外で偶数素数の和で表される偶数は無いことになります。と言うことは、ゴールドバッハ予想は「全ての6以上の偶数は、2個の奇素数の和で表すことが出来る」と等価である事になります。

以下のプログラムは、ほぼ定義のままに作成しています。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int isprime( unsigned long long n );

int main( int ac, char *av[] )
{
    unsigned long long  n, min_n, max_n, m1, m2;

    /*  コマンドラインから探索範囲を決定する    */
    if( ac < 3 )
        return;
    min_n = strtouq( av[1], NULL, 10 );
    min_n = min_n < 6 ? 6 : min_n;
    min_n = min_n % 2 == 1 ? min_n + 1 : min_n;
    max_n = strtouq( av[2], NULL, 10 );
    max_n = max_n % 2 == 1 ? max_n + 1 : max_n;

    /*  探索範囲の数を調べる    */
    for( n = min_n; n <= max_n; n += 2 ) {
        /*  足してnになる整数組(m1,m2)が共に素数か調べる    */
        for( m1 = 3, m2 = n - 3; m1 <= m2; m1 += 2, m2 -= 2 ) {
            if( isprime( m1 ) && isprime( m2 ) ) {
                printf( "%qu = %qu + %qu\n", n, m1, m2 );
                break;
            }
        }
        if( m1 > m2 )
            printf( "%qu NG\n", n );
    }
}

int isprime( unsigned long long n )
{
    unsigned long long  i, n2, pn2;

    /*  1は素数ではない */
    if( n == 1 )
        return( 0 );

    /*  2以外で2で割り切れたら合成数    */
    if( n != 2 && n % 2 == 0 )
        return( 0 );

    /*  sqrt(n)以上の出来るだけ小さい値を求める */
    pn2 = n2 = n;
    while( n2 * n2 > n || n2 * n2 < n2 ) {
        pn2 = n2;
        n2 /= 2;
    }
    if( pn2 >= n )
        n2 = n - 1;
    else
        n2 = pn2;

    /*  n2以下の奇数での剰余が0かどうか調べる   */
    for( i = 3; i <= n2; i += 2 ) {
        if( n % i == 0 )
            return( 0 );
    }

    /*  素数であった    */
    return( 1 );
}

素数の和で表されるまで単純に全ての数の組み合わせについて調べているので、処理速度は大変遅いです。素数の判定も単純な方法ですから2重に遅いことになります。それでも簡易なプログラムで安定して探索が出来ると言うメリットがあります。

実際に1億以下の数について調べてみましたが、全ての数においてゴールドバッハ予想が成り立ちました。しかし、1億以下の範囲を探索するのに約10時間掛かっているため、これ以上の範囲について探索を行うのは困難です。