#include <stdio.h>
#include <time.h>
#define MINNUM 3990000000
#define MAXNUM 4010000000

unsigned long modular_pow (unsigned long base,unsigned long exponent,unsigned long modulus)
{
  unsigned long result;

  if (modulus ==1)
      return 0;

  result=1;
  base=base%modulus;
  while (exponent>0) {
    if (exponent%2==1)
      result = (result*base) % modulus;

    exponent=exponent>>1;
    base= (base*base) % modulus;

  }

  return result;

}


int choose(int x)
{
  int a;

  if (x==1)
    a = 2;
  else if (x==2)
    a = 7;
  else if (x==3)
    a = 61;

  return a;
}


int main(void){
    double sttime, endtime ;

    unsigned long  x,q ;

    unsigned long a,d,s ;
    int w,flag,r,isprime;
    int p=0;


    sttime = (double) clock();

    for (s = MINNUM+1; s <= MAXNUM; s = s + 2){
      d = s - 1;
      r = 0;

      while (d % 2 == 0 ){
          d = d/2;
          r++;
      }

      isprime = 1;
      for(int i  = 1; i <= 3; i++){
        flag = 0;
        a = choose(i);

        x = modular_pow (a,d,s);
        //x=(a*q)%s;

        if ((x==1) || (x==s-1))
          continue;

        for(w=1; (w<=(r-1)); w++){
          //χ=χ^2mod n
          x = modular_pow(x,2,s);

          if (x==s-1){
            flag=1;
            break;
          }
        }

        if (flag==1)
          continue;
        else{
          isprime = 0;
          break;
        }

      }

      if (isprime)
          p=p+1;
    }

    endtime = (double) clock();
    //printf("Checking range [%d,%d] for primes\n",min,max);
    printf("Found  %d primes in ", p);
    printf("Time: %.3f secs\n", (endtime - sttime)/CLOCKS_PER_SEC);

}