/*
2000/12 素性のよい整数たち
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ ここに相異なる7数がある。そのうちの6数を選んでかけ合わせ│
 │,それに残りの1数を足すと素数になり,これはどの6数を選んで│
 │も成立しているという。このような7数の組み合わせはたくさん │
 │あるので,その7数の和が最小のものを見つけていただきたい。 │
 │なお,ここに登場する数はすべて正の整数とする。      │
 └─────────────────────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ 変数 MinOfSum は、解表示の判定基準であると同時に、7数の│
 │探索範囲も決めます。MinOfSum の初期値は定数S(=78)です。プ│
 │ログラムはx[0]〜x[6]を制御変数とした7重ループになります。│
 │x[0] のループは1から和の予想値が MinOfSum 以下の間繰り返│
 │します。x[1] のループは x[0]+1 から和の予想値が MinOfSum │
 │以下の間繰り返します。x[2]〜x[6]のループも同様です。和の予│
 │想値は残りの x[] が公差1の等差数列になると仮定して計算し │
 │ます。よって、ループの内側で x[] は、和が MinOfSum 以下に │
 │なる全ての7数を網羅します。               │
 │                             │
 │ 定数Sを小さくしすぎると、解が見つからなくなります。そこ│
 │で、Sを大きめにして実行し、解が見つかったらその和をメモし│
 │ます。そして、次に実行するときに、Sをメモした値にします。│
 │                             │
 │ 解となる7数は互いに素になります。これを利用して、ループ│
 │の中に条件を設定しました。方法は、あらかじめ2〜S-1の素因 │
 │数分解をして結果を配列に記録します。そして、例えば x[0] が│
 │6ならば、素因数の2と3のフラグを1にします。その後x[1]〜│
 │x[6] のどれかの素因数が2か3の場合、ループの次へ進むよう │
 │にしています。                      │
 │                             │
 │ 素数判定は、その数の平方根以下の素数全てで割り算を行い、│
 │余りが0でなければ素数とします。このとき、分母が素数かどう│
 │かをエラトステネスのふるいで判断します。         │
 └─────────────────────────────┘
 ┌─────────────────────────────┐
 │・感想                          │
 │                             │
 │ 9数以上の場合 unsigned long で扱えない大きな数を素数判 │
 │定する必要があります。最終的には、移植性のよい double で │
 │素数判定をするようにしました。double の代わりに __int64を │
 │使うと速くなる場合があります。              │
 └─────────────────────────────┘
*/
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>

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

#define N  7        /* 相異なる数の個数(3〜10) */
#define S (N==10?291:N==9?172:N==8?147:78) /* 総和の上限 */
#define P (N==10?1366806L:40217U) /* ふるいの大きさ */
char Sieve[P];      /* エラトステネスのふるい */
int Factors[S][8];  /* 素因数分解の結果     */
int Sum,MinOfSum=S; /* 解の総和とその最小値 */
double MaxOfNum;    /* 素数判定での引数の最高値 */

/*┌────────────────────────────┐
 │エラトステネスのふるいを実行し Sieve[] に結果を記録する │
 └────────────────────────────┘*/
void InitSieve(void)
{
    unsigned long i,j,s;

    for (i=0;i<P;i++) if (Sieve[(unsigned)i]==0)
     for (j=i+(s=i*2+3);j<P;j+=s) Sieve[(unsigned)j]=1;
}

/*┌───────────┐
 │x が素数ならば0を返す│
 └───────────┘*/
int IsNotPrime(const double x)
{
    if (x>MaxOfNum) MaxOfNum=x;
    if (x>4294967290.0) {
        double bound,divisor; unsigned i;
        if (x-floor(x/2)*2==0) return 1;
        bound=sqrt(x); divisor=3; i=0;
        for (;;) {
            if (divisor>bound) return 0;
            if (x-floor(x/divisor)*divisor==0) return 1;
            do { if (i<P) i++; divisor+=2; } while (i<P&&Sieve[i]);
        }
    }else{
        unsigned divisor,bound,i; unsigned long u=(unsigned long)x;
        if (u==2) return 0; else if ((u&1)==0||u==1) return 1;
        if (u<P*2L+2) return Sieve[(unsigned)((u-2)>>1)];
        bound=(unsigned)sqrt(x); divisor=3; i=0;
        for (;;) {
            if (divisor>bound) return 0;
            if (u%divisor==0) return 1;
            do { if (i<P) i++; divisor+=2; } while (i<P&&Sieve[i]);
        }
    }
}

/*┌───────────────────────┐
 │a を素因数分解し、結果を Factors[] に記録する │
 └───────────────────────┘*/
void InitFactor(void)
{
    int*p,a,x,divisor,prev; 

    for (a=2;a<S;a++) {
        x=a; divisor=2; prev=0; p=Factors[a];
        while (x!=1) if ((x%divisor)==0) {
            if (prev!=divisor) *p++=divisor;
            x/=divisor; prev=divisor;
        } else divisor++;
    }
}

/*┌──────┐
 │メインループ│
 └──────┘*/
void Loop(int z,char*flag,int*x)
{
    int*p,i;

    for (p=Factors[x[z-1]];*p;p++) flag[*p]=1;
    for (x[z]=x[z-1]+1;;x[z]++) {
        if (Sum+x[z]*(N-z)+(N-z-1)*(N-z)/2>MinOfSum) break;
        for (p=Factors[x[z]];*p;p++) if (flag[*p]) break;
        if (*p) continue;
#if N == 10
        if (z==4) 
             fprintf(stderr,"%d%3d%3d%3d%3d\r",
                     x[0],x[1],x[2],x[3],x[4]);
#elif N == 9
        if (z==1) fprintf(stderr,"%d%3d\r",x[0],x[1]);
#endif
        Sum+=x[z];
        if (z==N-1) for (;;) {
            double product=1;
            for (i=0;i<N;i++) product*=x[i];
            for (i=N-1;i>=0;i--)
             if (IsNotPrime(product/x[i]+x[i])) break;
            if (i>=0) break;
            printf("和=%d  ",MinOfSum=Sum);
            for (i=0;i<N;i++) printf(" %2d",x[i]);
            printf("\n"); fflush(stdout);
            break;
        } else Loop(z+1,flag,x);
        Sum-=x[z];
    }
    for (p=Factors[x[z-1]];*p;p++) flag[*p]=0;
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
void main(void)
{
    double StartTime=clock(); char flag[S]; int x[N];

    InitFactor(); InitSieve(); memset(flag,0,sizeof flag);
    for (x[0]=1;;x[0]++) {
        if (Sum+x[0]*N+(N-1)*N/2>MinOfSum) break;
        Sum+=x[0]; Loop(1,flag,x); Sum-=x[0];
    }
    printf(" Pに最低必要な値:%.0f   ",floor((sqrt(MaxOfNum)+1)/2));
    printf("実行時間:%.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
}