エマープを求める

エマープ

素数の各桁の数字を逆順にしても素数になるものをエマープといいます。13を逆順にした31も素数ですので、13と31はどちらもエマープです。ただし、逆順にした数が元の数と同じ場合はエマープではありません。回文素数はエマープにはならないわけですね。

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

int isprime( int n );
int isqrt( int x );

int main( int ac, char *av[] )
{
    int n, _n, n2, min_n, max_n;

    /*  コマンドラインから探索範囲を決定する    */
    if( ac < 3 ) {
        printf( "usage : emirp min_n max_n\n" );
        return( 1 );
    }
    min_n = strtol( av[1], NULL, 10 );
    min_n = min_n % 2 == 1 ? min_n + 1 : min_n;
    max_n = strtol( av[2], NULL, 10 );
    max_n = max_n % 2 == 1 ? max_n + 1 : max_n;

    /*  探索範囲の数を調べる    */
    for( n = min_n; n <= max_n; n++ ) {
        /* nが素数でなかったら次へ */
        if( !isprime( n ) )
            continue;
        /*  逆から読んだ数字が素数か調べる    */
        _n = n;
        n2 = 0;
        while( _n != -0 ) {
            n2 = n2 * 10 + _n % 10;
            _n /= 10;
        }
        /* 元の数と同じ場合はエマープではない */
        if( n == n2 )
            continue;
        if( isprime( n2 ) )
            printf( "%d\n", n );
    }

    return( 0 );
}

int isprime( int n )
{
    int i, n2, d;

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

    /*  2,3は素数 */
    if( n == 2 || n == 3 )
        return( 1 );

    /*  2,3で割り切れたら合成数    */
    if( n % 2 == 0 || n % 3 == 0 )
        return( 0 );

    /*  sqrt(n)を求める */
    n2 = isqrt( n );

    /*  n2以下の2,3の倍数以外での剰余が0かどうか調べる   */
    d = 2;
    for( i = 5; i <= n2; i += d, d = ( d == 2 ? 4 : 2 ) ) {
        if( n % i == 0 )
            return( 0 );
    }

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

int isqrt( int x )
{
    int s, t;

    if( x == 0 ) return 0;
    s = 1;
    t = x;
    while( s < t ) {
        s <<= 1;
        t >>= 1;
    }
    do {
        t = s;
        s = ( x / s + s ) >> 1;
    } while( s < t );

    return( t );
}

エマープの一覧

1000以下のエマープは13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199, 311, 337, 347, 359, 389, 701, 709, 733, 739, 743, 751, 761, 769, 907, 937, 941, 953, 967, 971, 983, 991の36個です。それ以上のエマープは別ファイルとして置いておきます。

• 1万以下(2KB)
• 10万以下(10KB)
• 100万以下(75KB)
• 1000万以下(626KB)
• 1億以下(1,660KB)
• 10億以下(13,256KB)

エマープの個数