/*
2001/02 III型素組数
coded by Isaku WADA
 ┌──────────────────────────────┐
 │  619737131179                      │
 │ この数は,なかからどの並んだ2桁の数をとっても素数になって │
 │おり,しかもすべて異なっている。このような数をU型素組数と呼│
 │ぶことにする。実はこの数は最大のU型素組数である。では,V型│
 │素組数(並んだ3桁のどれもが相異なる素数となっている数)の最 │
 │大を見つけてほしい。また,その最大値と同じ桁数には何個のV型│
 │素組数があるだろうか。                   │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │ まず、エラトステネスのふるいで素数の文字列表Table[168][3] │
 │を作ります。結果は、"002","003","005"..."997"のようになりま │
 │す。この時、ふるいとなる配列は、メモリ節約のためビット操作を│
 │行い、1バイトで8つの奇数を判定します。          │
 │                              │
 │ メイン関数は、3桁以上の素数"101"〜"997"それぞれについて、│
 │バッファに文字列をコピーし、関数sub(level)を引数1で呼び出し│
 │ます。                           │
 │                              │
 │ 関数sub(level)は再帰呼び出しをする関数です。引数levelは、 │
 │呼び出しの深さです。関数sub(level)は、まずlevelが今までの最 │
 │高値MaxLvを超えたかどうか判定します。もし、超えていれば、カ │
 │ウンタCountをクリアし、MaxLvを更新します。次に、MaxLvを更新 │
 │したかlevelがMaxLvと等しい場合は、Countを増やし、現在のバッ │
 │ファの内容を、最大素組数のバッファMaxBufへ転送します。そし │
 │て、素数"002"〜"997"についてループし、もし、この素数の左2桁│
 │とバッファの右2桁とが一致し、この素数が今までに出現していな│
 │ければ、下一桁をバッファに追加し、levelを一つ増やして自分自 │
 │身を呼び出します。                     │
 │                              │
 │ 関数sub(level)は、バッファの左から素数を昇順に割り当ててい│
 │くので、後に現れた素組数の方が必ず大きい素組数となります。従│
 │って、メイン関数のループが、最後の素数"997"の処理を終えれ  │
 │ば、MaxBufに最大素組数が求まります。            │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・感想                           │
 │                              │
 │ 最初は10191...のように0を含む素組数をカウントしないプログ│
 │ラムを作っていました。このことを除けば、今回は特に難しい所も│
 │なく、楽にプログラムを作ることができました。また、メモリを節│
 │約した結果、LSI-C86でもV型素組数にも対応できるようになりま │
 │した。                           │
 └──────────────────────────────┘
 Visual C++, Borland C++, LSI C-86, Turbo C で動作確認
 N=6 以上では LSI C-86, Turbo C ではメモリが確保できない
 N=7 の場合 Pentium III 550 MHz で15時間くらいかかった
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <time.h>

#define N 3 /* 素数の桁数 */

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌─────┐
 │変数の宣言│
 └─────┘*/
char*Flg;         /* エラトステネスのふるい */
char(*Table)[N];  /* 素数の文字列表("002","003","005" ... "997") */
int  Num;         /* 素数の総数(168) */
char Buf[100];    /* 調査中の素組数 */
char MaxBuf[100]; /* 最大素組数 */
int  Hist[100];   /* 過去に出現した素数の番号 */
int  MaxLv;       /* 最大素組数の長さ */
int  Count;       /* 最大素組数と同じ桁数の素組数の出現数 */

/*┌────────────┐
 │広さ size のメモリを確保│
 └────────────┘*/
void*Alloc(unsigned long size)
{
    void*p=size>=UINT_MAX?0:calloc((unsigned)size,1);

    if (p==0) { printf("メモリの確保に失敗\n"); exit(1); }
    return p;
}

/*┌──────────────────────────────┐
 │素数の文字列表 Table を作成する。素数の総数 Num も設定される│
 └──────────────────────────────┘*/
void MakeTable(void)
{
    unsigned long i,j,k,ad,size=1,bound=1;

    for (i=0;i<N;i++) bound*=10;
    ad=bound>>1; Flg=(char*)Alloc((ad>>3)+1);
    for (i=0;;i++) if ((Flg[(unsigned)(i>>3)]&(1<<(int)(i&7)))==0) {
        if ((j=i*2+3)>=bound) break; else size++;
        for (k=i+j;k<=ad;k+=j) Flg[(unsigned)(k>>3)]|=1<<(int)(k&7);
    }
    Table=(char(*)[N])Alloc(size*N+1); sprintf(Table[0],"%0*d",N,2);
    for (i=0,j=3,Num=1;j<bound;i++,j+=2)
     if ((Flg[(unsigned)(i>>3)]&(1<<(int)(i&7)))==0)
         sprintf(Table[Num++],"%0*lu",N,j);
}

/*┌──────────────────────────────┐
 │素数を割り当てられたら、自分自身を呼び出して、次を割り当てる│
 └──────────────────────────────┘*/
void sub(int level)
{
    int i,j;

    if (level>MaxLv)  { Count=0; MaxLv=level; }
    if (level==MaxLv) { Count++; strcpy(MaxBuf,Buf); }
    for (i=0;i<Num;i++) {
        for (j=0;j<N-1;j++) if (Buf[level+j]!=Table[i][j]) break;
        if  (j!=N-1) continue;
        for (j=0;j<level;j++) if (Hist[j]==i) break;
        if  (j!=level) continue;
        Hist[level]=i; Buf[level+N-1]=Table[i][N-1]; sub(level+1);
    }
    Buf[level+N-1]=0;
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
void main(void)
{
    int i; double StartTime=clock();

    MakeTable(); for (i=0;Table[i][0]=='0';i++);
    for (;i<Num;i++) { memcpy(Buf,Table[i],N); Hist[0]=i; sub(1); }
    printf("最大数:%s\n桁数:%d  組数:%d  ",MaxBuf,MaxLv+N-1,Count);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
}