//gcc -Wall -std=c99 fibonacci_prim.c -o fibonacci_prim
#include <stdio.h>

/*
 * Berechnen der Fibonacci-Folge
 * welche Zahlen der Folge sind Primzahlen?
 * 
*/

int main( int argc, char **argv ) {
	
	unsigned short int max;
	unsigned long int t;
	unsigned short int i;
	unsigned short int is_prim;
	unsigned long long fib0 = 0, fib1 = 1; 
	unsigned long long fib;

	/*
	 * Einlesen und ueberpruefen der Eingabe.
	 * Es wird eine positive 16Bit Zahl als Eingabe erwartet.
	*/	
	printf("Wie viele Fibonacci-Zahlen sollen berechnet werden (maximal 90): ");
	if( (scanf("%hu",&max) != 1) || (max > 90) ) {
		printf("Zahl muss zwischen 0 und 90 sein!\n");
		return 1;
	}
	
	//Die ersten beiden Zahlen der Folge sind fest
	printf( "Fibonacci-Nummer 0 ist 0.\n");
	printf( "Fibonacci-Nummer 1 ist 1.\n");
	
	//Berechne die Folge
	for( i=2; i <= max; i++ ) {
		fib = fib0 + fib1;
		fib0 = fib1;
		fib1 = fib;
		printf( "Fibonacci-Nummer %u ist %llu.", i, fib );
		
		//wir nehmen mal an es ist eine Primzahl
		is_prim = 1;
		
		//wenn dies zutrifft ist es keine Primzahl
		if ( (fib < 2) || ((fib > 2) && (fib % 2 == 0)) ) {
			is_prim = 0;
		}
		else {
			t = 3;
			//Teste alle ungeraden Zahlen zwischen 3 und sqrt(n)
			while ( is_prim && (t * t <= fib) ) {
				if (fib % t == 0) {
					is_prim = 0;
				}
				t += 2;
			}
		}
		if( is_prim ) {
			printf( " Dies ist eine Primzahl!");
		}
		printf("\n");
	
		
	}
	return 0;
	
}