#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define NTABLES 3
#define TSIZE   50000
#define PLIST   100000

int primetest(long n){
  long i, primecheck=1;

  for(i=2; i<sqrt((float)n); i++)
    if(n%i==0) {primecheck=0; break;}

  return primecheck;
}

long int offset[10]={350000001, 400000001, 450000001, 500000001, 550000001, 600000001, 650000001, 700000001, 750000001, 800000001};

char *filenames[10]={"primes350mil_up.fil","primes400mil_up.fil","primes450mil_up.fil","primes500mil_up.fil","primes550mil_up.fil","primes600mil_up.fil","primes650mil_up.fil","primes700mil_up.fil","primes750mil_up.fil","primes800mil_up.fil"};




main(){

  long int n;
  int primes[PLIST], i,j,currentprime, primecheck, start;
  int mat[NTABLES][TSIZE], size[NTABLES], currenttable,k, t;
  FILE *out;

  primes[0]=2;
  primes[1]=3;
  primes[2]=5;
  primes[3]=7;
  primes[4]=11;
  primes[5]=13;
  primes[6]=17;
  primes[7]=19;
  primes[8]=23;
  primes[9]=29;
  

  currentprime=10;

  for(i=5; currentprime<PLIST;i++){
    n=6*i+1;primecheck=1;
    for(j=2; j<currentprime && primes[j]*primes[j]<=n; j++){
      if((n%primes[j])==0){
	primecheck=0;
	break;}
    }

    if(primecheck==1) primes[currentprime++]=n;

    n=6*i+5;primecheck=1;
    for(j=2; j<currentprime && primes[j]*primes[j]<=n; j++){
      if((n%primes[j])==0){
	primecheck=0;
	break;}
    }

    if(primecheck==1) primes[currentprime++]=n;
  }
  

  currentprime=1;
  currenttable=0;

  for(currenttable=0; currenttable<NTABLES; currenttable++){
    size[currenttable]=primes[currentprime++];
    //printf("%d   ",size[currenttable]);
    mat[currenttable][0]=0;
    for(j=1; j<size[currenttable]; j++) mat[currenttable][j]=1;
    k=size[currenttable];
    size[currenttable]*=primes[currentprime];
    while(size[currenttable]<TSIZE){
      for(j=1; j<primes[currentprime]; j++)
	for(t=0; t<k; t++){
	  mat[currenttable][j*k+t]=mat[currenttable][t];
	}
      for(j=1;j<k; j++)
	{ mat[currenttable][j*primes[currentprime]]=0;}
      k=size[currenttable];
      currentprime++;
      size[currenttable]*=primes[currentprime];
    }
    size[currenttable]=size[currenttable]/primes[currentprime];
    // printf("table %d  curprime %d'th  %d size %d \n",currenttable, currentprime, primes[currentprime], size[currenttable]);

  }

 
  k=currentprime; //printf("k is %d\n", k);

  currentprime=0;

  // for(i=0; i<PLIST; i++)
  // printf("%d  ", primes[i]);

  //printf("%d   ", primes[PLIST-1]);


  //  for(start=0; start<10; start++){
  //out=fopen(filenames[start], "w");

   currentprime=0;
  
  for(n=32449831;currentprime<1000000; n+=2){
    primecheck=1; t=(int)sqrt((float)n);
    for(i=0; i<NTABLES; i++){
      if(mat[i][n%size[i]]==0) {primecheck=0; break;}
    }
    if(primecheck==1){
      for(i=k; i<PLIST && primes[i]<=t; i++){
	if(n%primes[i]==0) {primecheck=0; break;}
      }
    }
   

    if(primecheck==1) {
      printf("%d  ", n);
    currentprime++;
    }
  }
  printf("\n \n\n\n");

  // fclose(out);}
  
  
  
  fprintf(stderr, "last prime %d no of primes %d\n",n, currentprime );

}