フェルマー数は素数か

フェルマー数とはフェルマーが考案した素数を生成する式で、2²ⁿ+1(n≧0)というものです。

プログラムは例によって定義そのままに作成しています。べき乗をループを回して計算してしまっていますが、これはpow()がdouble型しか扱えない為です。

#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, m, l, i;

    /*  コマンドラインから指数を決定する    */
    if( ac < 2 )
        return;
    n = strtouq( av[1], NULL, 10 );

    /*  フェルマー数を求める    */
    m = 1;
    for( i = 0; i < n; i++ )
        m *= 2;
    l = 1;
    for( i = 0; i < m; i++ )
        l *= 2;
    l++;

    if( isprime( l ) )
        printf( "%qu OK\n", l );
    else
        printf( "%qu NG\n", l );
}

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 );
}

0,1,2,3,4の場合、それぞれ実際に素数となります。しかし、5の場合は4294967297となりこれは合成数でした。この先はどうかというと、式の形を見れば分かる通り値がとても大きくなる関数で6の場合で64bitで表せる範囲を超えてしまい、このプログラムではオーバーフローしてしまい求めることが出来ません。文献などによると、現在のところ5以上のフェルマー数については合成数しか見つかっていないそうです。