/*
2001/12 素数で割り切る素数の和
coded by Isaku WADA
 ┌────────────────────────────┐
 │5と71は,それぞれ自分未満の全素数の和を割り切ることが│
 │できる素数である。                   │
 │2+3=5=5×1                       │
 │2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67=568│
 │=71×8                         │
 │この条件を満たす素数を,5と71以外にもう1つ見つけてほ│
 │しい。                         │
 └────────────────────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │エラトステネスのふるいが基本です。プログラムは、3から369119│
 │までの奇数が素数かどうかを表すフラグの配列を持ちます。1バイ│
 │トに8個のフラグを詰め込むことにより、16ビットコンパイラの│
 │スモールモデルでも実行できるようになりました。       │
 │                              │
 │素数を見つける部分は、まず、2と3を素数とします。そして、奇│
 │数でかつ3の倍数全てのフラグを立てます。つぎに、フラグの立っ│
 │ていない最小の奇数5を素数とします。そして、奇数でかつ5の倍│
 │数全てのフラグを立てます。以下同様に、まだフラグの立っていな│
 │い最小の奇数を素数とし、奇数でかつ見つかった素数の倍数全ての│
 │フラグを立てることを繰り返すことにより、369119までの素数を見│
 │つけることができます。                   │
 │                              │
 │プログラムは、素数が見つかる都度に和sumを求めてゆきます。sum│
 │は32ビット整数だと桁あふれが起こるので、倍精度浮動小数点数│
 │を使いました。そして、sumを新しい素数で割り切ることができた │
 │ら表示します。割り切れたかどうかの判定は、sumを素数で割った │
 │浮動小数点数quotとfloor(quot)が等しいかどうかで行います。  │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・感想                           │
 │                              │
 │和の変数sumは、最初は__int64にしていました。しかし、__int64 │
 │やlong longは移植性がないので、doubleにしました。もちろん  │
 │doubleには53ビットという精度の限界があります。しかし、  │
 │415074643までに限れば、限界に達することはありませんでした。 │
 └──────────────────────────────┘
Visual C++, Borland C++, gcc, LSI C-86, Turbo C で動作確認
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.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 369119L /* 求める素数の上限(369119L,415074643L) */

/*┌──────┐
 │パズルを解く│
 └──────┘*/
void Solve(void)
{
    double sum=2.0,quot; long i,k,p; static char flag[(N>>4)+1];

    memset(flag,sizeof flag,0);
    for (i=0;i<(N-1)/2;i++)
     if ((flag[(unsigned)(i>>3)]&(1<<(i&7)))==0) {
         p=i+i+3; quot=sum/p; sum+=p;
         if (floor(quot)==quot) printf("%ld\n",p);
         for (k=i+p;k<N/2;k+=p) flag[(unsigned)(k>>3)]|=1<<(k&7);
     }
}

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

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