回文素数を求める

回文素数

素数の各桁の数字を入れ替えても素数になるものを回文素数と言います。11, 101などが回文素数です。

以下のプログラムは素数一覧にから回文素数を探索するものです。

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

#define BUF_SIZE  (1024)

int main( void )
{
    long long n, p, tmp;
    char buf[BUF_SIZE];

    /*  回文素数を探す  */
    while( fgets( buf, BUF_SIZE, stdin ) ) {
        if( ( p = strtoll( buf, NULL, 10 ) ) == 0 )
            continue;
        n = 0;
        tmp = p;
        while( tmp != 0 ) {
            n = n * 10 + tmp % 10;
            tmp /= 10;
        }
        if( p == n )
            printf( "%lld\n", p );
    }

    return( 0 );
}

(2026/3/9追記)

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

回文素数の一覧

2, 3, 5, 7 の一桁の素数は当然のことながら回文素数になります。1000以下の回文素数は先ほどの4つに加えて 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929 です。偶数桁の回文素数は11以外には存在しないので、10000以下の範囲は1000以下と同じになります。

• 10万以下(629B)
• 1000万以下(6KB)
• 10億以下(56KB)
• 1000億以下(550KB)
• 10兆以下(1,062KB)

回文素数の個数