/* 	goldbach.c  --  Matthias Jauernig, 13.11.03					*/
/* 	Programm überprüft Goldbach-Vermutung:						*/
/* 	jede gerade Zahl n>=6 ergibt sich aus der Summe zweier ungerader Primzahlen	*/

#include <stdio.h>

/* ---- istprim() - Funktion prüft, ob zahl prim ist; 0, wenn nicht; 1, wenn prim ----- */
char istprim(unsigned long long zahl){
	unsigned long long teiler;
	/* wir wollen mal nicht zu weit zählen, bis zahl/2 reicht, da teiler nur Teiler */
	/* von zahl sein kann, wenn er höchstens halb so groß wie zahl ist		*/
	/* außerdem von 3 an, da eine ungerade Primzahl nicht durch 2 teilbar ist	*/
	for(teiler=3; teiler<=zahl/2; teiler+=2)
		if(zahl%teiler==0)
			return 0;
	return 1;
}

/* ---- main() ------------------------------------------------------------------------	*/
int main(void){
	unsigned long long zahl, i, k;
	char prim=0;

	printf("Goldbach-Vermutung\n"
	       "==================\n\n"
	       "-> Jede gerade Zahl n>=6 ergibt sich aus der Summe zweier\n"
	       "   ungerader Primzahlen... - dies ueberprueft das Programm\n\n");
	do{
		printf("Zu pruefende Zahl?: ");
		scanf("%llu", &zahl);
	}while(((zahl%2!=0) && printf("Zahl muss gerade sein!\n\n"))
		|| ((zahl<6) && printf("Zahl muss >=6 sein!\n\n")));

	/* zahl muss in 2 ung. Primzahlen zerlegt werden, die in ihrer Summe wieder 	*/
	/* zahl ergeben; d.h. wir müssen im Intervall 3..zahl/2 erst nach einer Zahl i	*/
	/* suchen, welche ungerade und prim ist und dann nach einer zweiten Zahl k, die	*/
	/* sich aus k=zahl-i ergibt; diese ist ungerade, wenn i ungerade. muss jedoch 	*/
	/* ebenfalls prim sein; ist dies nicht der Fall, so muss man ein neues i suchen	*/
	for(i=3; i<=zahl/2 && !prim; i+=2)
		if(istprim(i)){	/* wenn i prim ist, dann betrachte die zweite Zahl k */
			k=zahl-i;
			prim=istprim(k); /* wenn k prim, dann endet die for-Schleife */
		}

	if(!prim){ /* wenn keine 2 Primzahlen gefunden wurden */
		printf("\nVerstoß gegen die Goldbach-Vermutung!\n");
		return 1;
	}

	i-=2; /* for-Schleife zählt einmal zuviel, daher wieder dekrementieren */
	printf("\nDie Zahl %llu entspricht der Goldbach-Vermutung:\n", zahl);
	printf("%llu = %llu + %llu\n\n", zahl, i, k);

	return 0;
}