エマープを求める

エマープ

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

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

int isprime( long long n );

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

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

    /*  探索範囲の数を調べる    */
    for( n = min_n; n <= max_n; n++ ) {
        /* nが素数でなかったら次へ */
        if( !isprime( n ) )
            continue;

        /*  逆から読んだ数字が素数か調べる    */
        tmp = n;
        n2 = 0;
        while( tmp != 0 ) {
            n2 = n2 * 10 + tmp % 10;
            tmp /= 10;
        }

        /* 元の数と同じ場合はエマープではない */
        if( n == n2 )
            continue;

        if( isprime( n2 ) )
            printf( "%lld\n", n );
    }

    return( 0 );
}

int isprime( long long n )
{
    long long i, 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 );

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

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

(2026/3/18追記)

int を long long に変更するとともに、ソースコードを少し整理しました。

探索範囲を広げられるようになったので、100億以下のエマープを求めて掲載しました。合わせてエマープの個数と素数の個数の比率も計算してみました。数が大きくなるとエマープの存在確率は下がっていくんですね。なんとなく一定の比率で存在しそうな気がしたので意外でした。

エマープの一覧

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)
• 100億以下(108,252KB)

エマープの個数