/*
2003/01 素数団
coded by Isaku WADA
 ┌────────────────────────────┐
 │ 相異なる10個の数がある。このうちの9個を選んで足し合│
 │わせたところ素数となった。さらにほかのどの9個を選んでも│
 │やはり素数となった。これを満足する10個の数の組み合わせ│
 │はたくさんあるが,その中で「10個の数の総和がもっとも小│
 │さい組み合わせ」(同じ総和で複数ある場合はすべて)をお答え│
 │いただきたい。                     │
 │ なお,10個の数の総和は素数である必要はない。ここで扱│
 │う数はすべて正の整数とする。              │
 └────────────────────────────┘
 ┌─────────────────────┐
 │解答:1 3 7 9 19 21 27 33 37 43 総和:200 │
 └─────────────────────┘
 ┌──────────────┬──────┬───────┐
 │コンパイラ         │実行時間  │ファイルサイズ│
 ├──────────────┼──────┼───────┤
 │Microsoft Visual C++ 6.0  │0.00000859秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.00000781秒│ 35328 byte │
 │Borland C++ 5.5.1 for Win32 │0.00000828秒│ 53760 byte │
 │gcc-2.953(djgpp)      │0.00000879秒│ 109172 byte │
 │gcc-2.953(cygwin)      │0.00000938秒│ 20050 byte │
 │LSI C-86 Ver 3.30 試食版  │0.00002800秒│ 13690 byte │
 │Turbo C Ver 1.5(small model)│0.00009060秒│ 11244 byte │
 ├──────────────┼──────┴───────┤
 │ CPU:Pentium4 2.52GHz │   OS:Windows XP    │
 └──────────────┴──────────────┘
 ┌───────────────────────────────┐
 │・プログラムの説明                      │
 │                               │
 │求める10個の数をXiとし、その内の9個の和で得られる10個  │
 │の素数ΣX−XiをPiとします。ΣP=ΣΣX−ΣXとなり、   │
 │ΣX=ΣP/9を得ます。Piが与えられて、ΣPが9で割り切れ  │
 │ればXi=ΣP/9−Piとして、Xiを得ることができます。    │
 │(ただし、全てのXiについて、Xi>0)             │
 │                               │
 │プログラムはエラトステネスのふるいを使って、200未満の46 │
 │個の素数を生成します。そして、そこから10個を選びます。この │
 │とき、P0>P1> … >P9となるように選びます。Piを選ぶと同 │
 │時にΣPも求めてゆき、10個選んだ時点で、ΣPが9で割り切れ │
 │たら、後述する発見処理をします。               │
 │                               │
 │変数MinOfSumは、今まで発見してきた解の中で1番小さなΣXを記 │
 │録します。プログラムの先頭ではMinOfSumを大きな値に設定してお │
 │き、発見処理はMinOfSumよりも小さなΣXが得られるたびに    │
 │MinOfSumを小さなΣXへ更新し、ログをクリアしてゆきます。その │
 │うえでΣXがMinOfSumと等しいならば、ログにXiのすべてを記録し │
 │てゆきます。                         │
 │                               │
 │枝刈りは、条件Xi>0を使います。P0>P1> … >P9 なので、 │
 │例えばP3を選んでいる時に、ΣPの予測値            │
 │P0+P1+P2+P3*(10−3)がP0*9よりも小さい場合は、最 │
 │終的にX0が0以下になることが確定してしまうので、そこから先は │
 │調べないようにします。この枝刈りを行うことで、条件Xi>0が保 │
 │証されます。                         │
 ├───────────────────────────────┤
 │・感想                            │
 │                               │
 │プログラムを工夫して、全体の数を増やすことは容易にできるよう │
 │になりました。試しに、全体の数を50にしてみたところ、11分 │
 │かけて総和が10344の解が54個見つかりました。一方、全体 │
 │の数を10にしたまま、選ぶ個数を8個や7個に変えるのは、計算 │
 │時間の短縮がうまくゆかず、解を見つけることができませんでした。│
 └───────────────────────────────┘
*/

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

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define N 10  /* 相異なる数の個数             10/  44/   50 */
#define P 200 /* 使用する素数の上限          200/7592/10344 */
#define M 46  /* 使用する素数の数(Pで決まる) 46/ 965/ 1270 */
#define L 1   /* ログの大きさ                  1/ 152/   54 */

/*┌─────┐
 │変数の宣言│
 └─────┘*/
unsigned Primes[M];   /* P以下の素数を全て記録する          */
int      NumOfPrimes; /* P以下の素数の総数                  */
int      Config[N];   /* 素数の選び方                        */
long     SumOfPrimes; /* 選ばれた素数の総和                  */
long     Bound;       /* 枝刈りの条件(一番大きな素数のN-1倍) */
unsigned Log[L][N];   /* 解のログ                            */
int      NumOfSol;    /* ログにたまった解の数                */
int      MaxOfLog;    /* ログの大きさの最大値                */
unsigned MinOfSum;    /* 最小和                              */

/*┌───────────┐
 │エラトステネスのふるい│
 └───────────┘*/
void DoSieve(void)
{
    unsigned i,j,p; static char PrimeFlag[(P>>1)+1];

    memset(PrimeFlag,0,sizeof PrimeFlag);
    NumOfPrimes=1; Primes[0]=2;
    for (i=0;i<(P-1)/2;i++) if (PrimeFlag[i]==0) {
        if (NumOfPrimes==M) { printf("M が小さい\n"); exit(1); }
        Primes[NumOfPrimes++]=p=i+i+3;
        for (j=i+p;j<P/2;j+=p) PrimeFlag[j]=1;
    }
    /* 大きい順に並び替える */
    for (i=0,j=NumOfPrimes-1;i<j;i++,j--)
    { p=Primes[i]; Primes[i]=Primes[j]; Primes[j]=p; }
}

/*┌────┐
 │解の表示│
 └────┘*/
void Print(void)
{
    int i,k;

    for (k=0;k<NumOfSol;k++) {
        printf("No.%d:",k+1);
        for (i=0;i<N;i++) printf(" %u",Log[k][i]);
        printf("\n");
    }
    printf("MinOfSum=%u  ",    MinOfSum);
    printf("NumOfPrimes=%d  ", NumOfPrimes);
    printf("MaxOfLog=%d\n",    MaxOfLog);
}

/*┌────┐
 │発見処理│
 └────┘*/
void Check(void)
{
    int i; unsigned sum;

    sum=(unsigned)(SumOfPrimes/(N-1));  /* 10個の数の総和を求める */
    if (sum<MinOfSum) { NumOfSol=0; MinOfSum=sum; } /* 最小和更新 */
    if (sum==MinOfSum) {                            /* ログに追加 */
        if (NumOfSol==L) { printf("L が小さい\n"); exit(1); }
        for (i=0;i<N;i++) Log[NumOfSol][i]=sum-Primes[Config[i]];
        NumOfSol++;
        if (NumOfSol>MaxOfLog) MaxOfLog=NumOfSol;
    }
}

/*┌───────────────┐
 │パズルを解く(再帰呼び出しあり)│
 └───────────────┘*/
void Solve(int level,int top)
{
    int i; unsigned p;

    if (level==0) { DoSieve(); MinOfSum=UINT_MAX; } /* 初期化 */
    if (level==N) {
        if (SumOfPrimes%(N-1)==0) Check(); /* 発見処理 */
        return;
    }
    for (i=top;i<NumOfPrimes;i++) {
        p=Primes[i];                           /* 素数を選ぶ */
        if (level==0) Bound=(long)p*(N-1);     /* 条件の設定 */
        if ((SumOfPrimes+(long)p*(N-level))<=Bound)
            return;                      /* 条件による枝刈り */
        Config[level]=i;    SumOfPrimes+=p;
        Solve(level+1,i+1); SumOfPrimes-=p;
    }
}

/*┌────────────────────┐
 │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

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(int argc,char**argv)
{
    double StartTime=clock(); long i,num;

    if (argc==2) num=atol(argv[1]); else num=1;
    for (i=0;i<num;i++) Solve(0,0);
    Print();
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}