#include <stdio.h>
#include <math.h>
long long int a1,b,c,x,x1;
int i,n,k,t;
int a[1000000],primes[1000000];
main()
{ printf("input size\n ");
  scanf("%d",&n);
  t=clock();
/***  This part generates odd primes upto n by 
      Eratosthenes sieve ***/
  for(i=1;i<=n;i++) a[i]=0;
  for(i=2;i<=n;i+=2)a[i]=1;
  for (i=3;i*i<=n;i+=2){
    for(k=i;i*k<=n;k++){  /*** multiples of i are excluded ***/
    a[i*k]=1; }  /*** a[j]==1 means j is not a prime ***/
  }
  k=1;
  for (i=1;i<=n;i++) {if(a[i]==0){
    primes[k]=i; k++;
    }
  }
/*** We choose three coefficients from large primes ***/ 
/*** The choice of a1,b,c, and x is rather arbitrary ***/
  a1=primes[k-10]; b=primes[k-3]; c=primes[k-2];
/*** Seed x is also a latge prime ***/
/*** By changing the seed, you can generate different
     random numbers ***/
  x=primes[k-20];
  x1=x;
  printf("seed= %lld\n",x);
/*** This part is the linear congruential method ***/
  for(i=1;i<=n;i++){
    x=(a1*x + b)%c; /*** These are done in double precision ***/
    a[i]=x;
    if(x==x1){printf("pirod= %d\n",i); getchar();}
  }
/*** Random numbers are given in array a ***/
  for(i=1;i<=10;i++)printf("%d ",a[i]);
  printf("\n");
/*** We can use a[1], ..., a[period-1] for random numbers ***/
}