#include <stdio.h>
#include <math.h>
#include <time.h>

long long unsigned p_pt(long long unsigned t)
{
  long long unsigned a=5;
  while (a*a<=t)
    {
      if (t%a==0)
        return -1;
      if (t%(a+2)==0)
        return -1;
      a=a+6;
    }
  return 1;
}

/* do we have a prime number ? */
long long unsigned am_primetest(long long unsigned t)
{
  long long unsigned a=5;
  if (t<4)
    {
      if (t==2)
        return 1;
      if (t==3)
        return 1;
      return -1;
    }
  if (t%2==0)
    return -1;
  if (t%3==0)
    return -1;
  while (a*a<=t)
    {
      if (t%a==0)
        return -1;
      if (t%(a+2)==0)
        return -1;
      a=a+6;
    }
  return 1;
}

/*  Goldbach's Conjecture  */
long long unsigned am_goldbach(long long unsigned a, long long unsigned *p)
{
  long long unsigned e=5,k;
  if (am_primetest(a-3)==1) 
    { 
      p[0]=3; 
      p[1]=a-3; 
      return 1; 
    } 
  k=a/2+1; 
  while(e<k) 
    { 
      if (p_pt(e)==1) 
        { 
          if(am_primetest(a-e)==1) 
            { 
              p[0]=e; 
              p[1]=a-e; 
              return 1; 
            } 
        } 
      e=e+2; 
      if (p_pt(e)==1) 
        { 
          if(am_primetest(a-e)==1) 
            { 
              p[0]=e; 
              p[1]=a-e; 
              return 1; 
            } 
        } 
      e=e+4; 
    } 
  return -1; 
} 
 
int main(void) 
{ 
  long long unsigned von, bis, i;
  clock_t start, ende;
  long long unsigned buffer[2];
 
  printf("Goldbach-Vermutung\n" 
         "==================\n\n" 
         "-> Jede gerade Zahl groesser gleich 6 ergibt sich aus der Summe\n"
         "   zweier ungerader Primzahlen... - dies ueberprueft das Programm\n\n"); 
  printf("Zu pruefenden Bereich eingeben:\n"); 
 
  do 
    { 
      printf("1. Untere Grenze: "); 
      scanf("%llu", &von);
    } 
  while(von%2!=0 && printf("Zahl muss gerade sein!\n")
  	|| von<6 && printf("Zahl muss groesser gleich 6 sein!\n"));
  printf("2. Obere Grenze: "); 
  scanf("%llu", &bis);
 
  start = clock(); 

  /* pruefe alle Zahlen im Bereich [von...bis] */
  for(i=von; i<=bis; i+=2) 
    {
      printf("\r%6.3f%% bearbeitet...", i/(float)bis*100);
      if ( am_goldbach(i,buffer) == -1)
        {
          printf("Goldbach-Vermutung ist falsch! ( Zahl %llu )\n", i);break;
        }/*
      else
        {
          printf("Goldbach is right: %i = %i + %i\n", i, buffer[0], buffer[1]);
        }*/
    }
 
  ende = clock(); 
 
  printf("\nAlle Zahlen im Bereich [%llu...%llu] entsprechen "
         "der Goldbach-Vermutung!\n\n", von, bis); 
  printf("Benoetigte Zeit: %10.3f Sek\n\n", 
         (ende-start)/(double)CLOCKS_PER_SEC); 
 
  return 0; 
}