素数の各桁の数値を数える

素数の各桁の数値を数える

素数の各桁が何種類の数字からなっているかを数えてみます。例えば11は1種類の数字からなっていて、13は2種類からなっているというようにカウントします。

以下のプログラムは素数一覧に対して素数の各桁の数値を数えるものです。

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

int countdigit( int n );

int main( int ac, char *av[] )
{
    int count, n;
    char buf[1024];

    while( fgets( buf, 1024, stdin ) ) {
        n = strtol( buf, NULL, 10 );
        count = countdigit( n );
        printf( "%d %d\n", n, count );
    }

    return( 0 );
}


int countdigit( int n )
{
    int     i, types[10], count;
    char    buf[1024];

    for( i = 0; i < 10; i++ )
        types[i] = 0;

    sprintf( buf, "%d", n );
    for( i = 0; i < strlen( buf ); i++ )
        types[buf[i] - '0']++;

    count = 0;
    for( i = 0; i < 10; i++ )
        if( types[i] != 0 )
            count++;

    return( count );
}

1億以下の素数の中で、1種類の数字だけからなるものは2,3,5,7,11だけでした。1桁の場合は必ず1種類なのは当たり前ですから、実質11のみという事になります。1以外の数字が1種類でなる素数は有り得ませんが、111111のような素数がもっとあるかと予想したのですが。

2種類以上は数が多すぎて全てを列挙できませんので、それぞれの素数の数だけを記します。

各桁の数字の種類の数 1 2 3 4 5 6 7 8 9 10
素数の個数 5 1087 53901 582793 1896171 2248373 888615 90510 0 0

(2012/2/15追記)

素数一覧を10億まで求めたので、こちらも10億以下にデータを更新しました。

各桁の数字の種類の数 1 2 3 4 5 6 7 8 9 10
素数の個数 5 1918 153410 2404651 11337828 20444470 13280421 3079604 145227 0

あおやぎのさいと2.0初歩の整数論プログラミング