// goldbach.c  --  unter GPL, (c) RTC @ 2003; <linux-related@web.de>
// Programm zur Überprüfung der Goldbach-Vermutung:
// jede gerade Zahl größer 2 ergibt sich aus der Summe zweier Primzahlen
// -- mit Effizienzausgabe (verbrauchte CPU-Zeit)

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

int main(void){
	long int von, bis, i, j, k, teiler;
	bool ist_prim=1;
	clock_t start, ende;

	printf("Goldbach-Vermutung\n"
	       "==================\n\n"
	       "-> Jede gerade Zahl groeßer als 2 ergibt sich aus der Summe\n"
	       "   zweier Primzahlen... - dies ueberprueft das Programm\n\n");
	printf("Zu pruefenden Bereich eingeben:\n");

	do {
		printf("1. Untere Grenze: ");
		scanf("%ld", &von);
	} while(von<0 && printf("Zahl muss positiv sein!\n"));
	printf("2. Obere Grenze: ");
	scanf("%ld", &bis);
	
	start = clock();	

	if(von<=2) von=4;		// 4 ist die erste gerade Zahl > 2
	else if(von%2 !=0)		// wenn "von" ungerade...
		++von;			// ... dann mache sie gerade!

	/* pruefe alle Zahlen im Bereich [von...bis] */
	for(i=von; i<=bis; i+=2){	
		printf("\r%6.3f%% bearbeitet...", i/(float)bis*100);
		/* pruefe die jeweilige Zahl j auf die Goldbach-Vermutung */
		for(j=2; j<i; ++j){
			ist_prim=1;
			/* pruefe, ob erste Zahl j eine Primzahl ist */
			for(teiler=2; teiler<=j/2; ++teiler)
			/* wenn Ausdruck wahr, dann keine Primzahl */
				if(j%teiler==0){
					ist_prim=0;
					break;
				}
			/* wenn keine Primzahl, dann pruefe naechste Zahl */
			if(!ist_prim) continue;
			
			/* pruefe die zweite Zahl k, die die Differenz
			   zwischen i und j darstellt */
			k=i-j;
			for(teiler=2; teiler<=k/2; ++teiler)
			/* wenn Ausdruck wahr, dann keine Primzahl */
				if(k%teiler==0){
					ist_prim=0;
					break;
				}
			
			/* wenn Goldbach-Zahl gefunden, dann fahre 
			   mit naechstem i fort */
			if(ist_prim) break;
		}
		if(!ist_prim){
			printf("\nVerstoß gegen die Goldbach-Vermutung!\n");
			return 0;
		}
	}

	ende = clock();	

	printf("\nAlle Zahlen im Bereich [%ld...%ld] entsprechen "
	       "der Goldbach-Vermutung!\n\n", von, bis);
	printf("Benoetigte Zeit: %10.3f Sek\n\n", 
		(ende-start)/(double)CLOCKS_PER_SEC);	 
	return 0;
}