/* Programm prüft die Goldbach-Vermutung an einer Zahl zahl			*/
/* Grundlage für den Algorithmus bildet die Webseite http://www.2357.a-tu.net/,	*/
/* die eine Library zur Berechnung von Primzahlen bereitstellt;			*/
/* großer Vorteil des ALgorithmus' dieser Seite ist, dass er für größere	*/
/* Zahlen nicht quadratisch, sondern annähernd linear skaliert im Gegensatz	*/
/* zu einfachen Algorithmen zur Primzahl-Berechnung				*/
/* somit lassen sich auch höchste gerade Zahlen in hoher Geschwindigkeit auf 	*/
/* die Goldbach-Vermutung hin überprüfen					*/

/* --- includes --------------------------------------------------------------- */
#include <stdio.h>
#include <math.h>

/* --- p_pt() --- Hilfsfunktion für am_goldbach() -----------------------------	*/
char 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;
}

/* --- am_primetest() --- prüft eine übergebene Zahl auf Primalität -----------	*/
char 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;
}

/* --- am_goldbach() --- prüft eine Zahl auf die Goldbach-Vermutung -----------	*/
char 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; 
} 


/* --- main() -----------------------------------------------------------------	*/
int main(void){
  long long unsigned zahl, 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"); 

 do{
      printf("Zu pruefende Zahl eingeben: ");
      scanf("%llu", &zahl);
 }while((zahl%2!=0 && printf("Zahl muss gerade sein!\n"))
  	|| (zahl<6 && printf("Zahl muss groesser gleich 6 sein!\n")));

 if(am_goldbach(zahl, buffer)==-1)
      printf("Die Zahl %llu entspricht nicht der Goldbach-Vermutung!\n", zahl);
 else
      printf("Die Zahl %llu entspricht der Goldbach-Vermutung:\n"
      	     "%llu = %llu + %llu\n", zahl, zahl, buffer[0], buffer[1]);

 return 0;
}