回文素数
素数の各桁の数字を入れ替えても素数になるものを回文素数と言います。11, 101などが回文素数です。
以下のプログラムは素数一覧にから回文素数を探索するものです。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int countdigit( int n );
int main( int ac, char *av[] )
{
int n, _n, n2;
char buf[1024];
while( fgets( buf, 1024, stdin ) ) {
n = _n = strtol( buf, NULL, 10 );
n2 = 0;
while( _n != -0 ) {
n2 = n2 * 10 + _n % 10;
_n /= 10;
}
if( n == n2 )
printf( "%d\n", n );
}
return( 0 );
}
回文素数の一覧
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万以下 | 113個 |
1000万以下 | 781個 |
10億以下 | 5953個 |
1000億以下 | 47,995個 |
10兆以下 | 401,696個 |