//gcc -Wall primzahl.c -o primzahl
#include <stdio.h>

/*
 * Ist n eine Primzahl?
 * probedivision => http://de.wikipedia.org/wiki/Probedivision
 * 
*/
int main( int argc, char **argv ) {
	
	unsigned long int n;
	unsigned long int t;
	unsigned short int is_prim;
	
	//Einlesen und ueberpruefen der Eingabe.
	printf("Geben Sie eine Zahl ein: ");
	if( scanf("%lu",&n) != 1 ) {
		printf( "Bitte geben Sie eine positive ganze Zahl ein!\n" );
		return 1;
	}
	
	do {	
		//wir nehmen mal an es ist eine Primzahl
		is_prim = 1;
		
		//wenn dies zutrifft ist es keine Primzahl
		if ( (n < 2) || ((n > 2) && (n % 2 == 0)) ) {
			is_prim = 0;
		}

		t = 3;
		//Teste alle ungeraden Zahlen zwischen 3 und sqrt(n)
		while ( is_prim && (t * t <= n) ) {
			if (n % t == 0) {
				is_prim = 0;
			}
			t += 2;
		}
		
		//n war keine Primzahl, vielleicht ist n+1 eine Primzahl?
		if( !is_prim ) {
			n++;
		}
	}
	while(!is_prim);
	
	//Ausgeben	
	printf( "%lu ist eine Primzahl!\n", n );
	
	return 0;
}