//***************************************************//
// 数学の部屋                                       *//
//     ２つの素数の差  検査ソフト                 　*//
//     Copyrighted by Y/M.Ojisan 2003/7/23          *//
//***************************************************//

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#include <string.h>
#include <time.h>

// 検査最大　２Ｎ＝�剪l=４Ｅ１３
// Ｐ１素数　差代値 8196
// エラトステネスの篩用素数マップ １６Ｍまで　ie 256T
// 素数マップビット対応　INTベース　3は　0番地　0bit
//       Pは　[(P-3)/64]番地　{ (P-3)/2 mod 32 }bit
//       LAST P=2^24+1  2^17-1番地　 31bit int[256k]
FILE *fp;

#define SIZEofINT 32
#define Pstart 3
#define PEend   ((1<<24)+1)
#define GUend    ((_int64)400000000000000)
#define ERATOS_AREA ((PEend-1)/2/SIZEofINT)
#define CHECKSIZE (1600000)
#define MASKSIZE ((8196)/16)

unsigned int PEmap[ERATOS_AREA];
unsigned int PImap[CHECKSIZE];
unsigned int PMmap[SIZEofINT][MASKSIZE];
unsigned int PVmap[CHECKSIZE];

unsigned int bitmap[SIZEofINT],ibitmap[SIZEofINT];
unsigned int PEmask[SIZEofINT][SIZEofINT];
         int PE_k[SIZEofINT][SIZEofINT];
unsigned int FF=-1;

int reverse(int X)
{
	int Y=0,i;
	for(i=0;i<SIZEofINT;i++)
	{Y=(Y<<1)|(1&X);X>>=1;}
	return Y;
}
void init()
{
	int i,j,p,bit,pp;
	int k,dj,dbit;
//bitmap
	for(i=0;i<SIZEofINT;i++) {bitmap[i]=1<<i;ibitmap[i]=FF-bitmap[i];}
//PEmask
	for(p=0;p<SIZEofINT;p++)
   		for(i=0;i<SIZEofINT;i++)
		{
			PEmask[p][i]=FF;
			PE_k[p][i]=FF;
        }
	for(p=3;p<SIZEofINT*2;p+=2)
	{
		pp=p+p;
//		for(j=p;j<=(2*SIZEofINT*SIZEofINT-1)*2+Pstart;j+=pp)
		for(j=p;j<=p*(SIZEofINT*2-1);j+=pp)
		{
			i=(j-Pstart)/2/SIZEofINT;bit=((j-Pstart)/2) % SIZEofINT;
			PEmask[p][i] ^=bitmap[bit];
			PE_k[p][bit]=i;
		}
	}
//エラトステネスふるい初期化
	for(i=0;i<ERATOS_AREA;i++) PEmap[i]=FF;
//エラトステネスふるい作成
	for(p=Pstart;p<=PEend;p+=2) {i=(p-Pstart)/2/SIZEofINT;bit=((p-Pstart)/2) % SIZEofINT;
    if( (PEmap[i] & bitmap[bit])!=0)
	{
		pp=p+p;
		if(p<SIZEofINT)
		{
			k=0;
			for(i=0;i<ERATOS_AREA;i++)
			{
				PEmap[i]&=PEmask[p][k++];
				if(k==p) k=0;
			}
            PEmap[0]|=bitmap[bit];
		}else
		{
			j=p+pp;
			i=(j-Pstart)/2/SIZEofINT;bit=((j-Pstart)/2) % SIZEofINT;
			dj=p/SIZEofINT;
			dbit=p%SIZEofINT;
			for(;j<=PEend;j+=pp)
			{
				PEmap[i]&=ibitmap[bit];
				i+=dj;
				bit+=dbit;
				if(bit>=SIZEofINT){bit-=SIZEofINT;i++;}
			}
		}
	}
    }
}
void check(__int64 Qs,int AREA, unsigned int Page[])
{
	int i,bit,T,q,qmax,Er=0;
	_int64 p;
	for(i=0;i<AREA;i++)
	for(bit=0;bit<32;bit++)
	{
		p=Qs+2*(bit+32*i);
		T=Page[i]&bitmap[bit];
		qmax=(int)sqrt((double)p)+1;
		for(q=3;q<=qmax;q+=2)
		{
          if((p %q)==0)
		  {
			  if(T!=0) {printf("F-Error @ %I64d\n",p);Er++;}
			  goto Ex;
		  }
		}
		if(T==0) {printf("T-Error @ %I64d\n",p);Er++;}
Ex:;
    } 
	printf("checkend %d\n",Er);getch();
}

void make_page(_int64 Qtop,int PageSize)
{
  _int64 Qend,j;
  int Pend,p,i,di,bit,dbit,pp,k,X;
  unsigned int *a,*A,*b,*B;

  Qend = Qtop-2+(2*SIZEofINT)*PageSize;
  Pend = (int)sqrt((double)Qend)+1;

  for(p=3;p<=Pend;p+=2)
  if( (PEmap[(p-3)/2/SIZEofINT] & bitmap[((p-3)/2)%SIZEofINT])!=0)
  {
		pp=p+p;
		j=(Qtop+p-1)/p;
		if(j==1) j=3;
		if(j%2==0) j=j*p+p;else j=j*p;
    	X=(int)(j-Qtop)/2;
		if(p==3)
		{
			bit=X % SIZEofINT;
			k=PE_k[3][bit];
			for(i=0;i<PageSize;i++)
			{
				PImap[i]=PEmask[3][k++];
				if(k==3) k=0;
			}
            if(Qtop==3) PImap[0]|=bitmap[0];
		}
		else 
		if(p<SIZEofINT && Qtop>=SIZEofINT)
		{
			bit=X % SIZEofINT;
			k=PE_k[p][bit];
			for(i=0;i<PageSize;i++)
			{
				PImap[i]&=PEmask[p][k++];
				if(k==p) k=0;
			}
  		}else
		{
			i=X/SIZEofINT;bit=X % SIZEofINT;
			di=p/SIZEofINT;
			dbit=p%SIZEofINT;

			a=PImap+i;
			A=PImap+PageSize;
			b=ibitmap+bit;
			B=ibitmap+SIZEofINT;
			while(a<A)
			{
				(*a)&=(*b);
				a+=di;
				b+=dbit;
				if(b>=B){b-=SIZEofINT;a++;}
			}
		}

  }
}
_int64 solutions(_int64 Qtop,int PageSize,int MaskSize);
void main()
{
	time_t T1,T2;double duration;
	int I,J;
    _int64 C=3;


	T1=clock();
	{
		init();
        for(I=0;I<MASKSIZE;I++)
			PMmap[SIZEofINT-1][I]=reverse(PEmap[I]);
        for(J=0;J<SIZEofINT-1;J++)
        for(I=0;I<MASKSIZE;I++)
		{
			PMmap[J][I]=PMmap[SIZEofINT-1][I]>>(SIZEofINT-J-1);
            if(I>=1)
			PMmap[J][I]|=PMmap[SIZEofINT-1][I-1]<<(J+1);
		}
	}
	T2=clock();
	duration = (double)(T2-T1) / CLOCKS_PER_SEC;
    cprintf("%f(sec) Input Pstart>\n",duration);
    scanf("%I64d",&C) ;if((C%2)==0) C=C+1;if(C<3) C=3;
	
	fp=fopen("out.txt","a");

	while(C<GUend+3)
	{		
		T1=clock();
		make_page(C,CHECKSIZE);
 //   	check(C,CHECKSIZE,PImap);
		for(I=0;I<CHECKSIZE;I++) PVmap[I]=0;
     	T2=clock();
	    duration = (double)(T2-T1) / CLOCKS_PER_SEC;
        cprintf("%fsec ",duration);
	    C=solutions(C,CHECKSIZE,MASKSIZE);
     	T2=clock();
	    duration = (double)(T2-T1) / CLOCKS_PER_SEC;
        cprintf("%fsec\n",duration);
        fprintf(fp,",%f (sec) \n",duration);
        fflush(fp);
    }
	fclose(fp);
	getch();
}

_int64 solutions(_int64 Qtop,int PageSize,int MaskSize)
{
	_int64 DELTAtop=Qtop-3,DELTAend;
	int    pos1=-1,pos2,bit,i,dpmax=0,imin;
	unsigned int    temp,*pm;
    
	for(pos2=0;pos2<PageSize;pos2++)
	{
		temp=PImap[pos2];
		for(bit=0;bit<SIZEofINT;bit++)
		if((bitmap[bit] & temp)!=0) 
		{
			imin=pos2-MaskSize;if(imin<pos1) imin=pos1;
			pm=&(PMmap[bit][pos2]);
			for(i=pos2;i>imin;i--)
				PVmap[i]|=*(pm-i);
		}
		while(PVmap[pos1+1]==FF) pos1++;
		if(pos2-pos1>dpmax) dpmax=pos2-pos1;
	}

    DELTAend=DELTAtop-2+(2*SIZEofINT)*pos1;
	if(PageSize-MaskSize<=pos1)
	{
		cprintf("GOOD OK=%I64d -- %I64d %d\n",DELTAtop,DELTAend,64*dpmax);
		fprintf(fp,"GOOD OK=,%I64d,%I64d,%d",DELTAtop,DELTAend,64*dpmax);
	}
	else 
	{
		cprintf("BAD  OK=%I64d -- %I64d %d\n",DELTAtop,DELTAend,64*dpmax);
		fprintf(fp,"BAD  OK=,%I64d,%I64d,%d",DELTAtop,DELTAend,64*dpmax);		
	}
	return (DELTAend+5);
}