int n=0;
int *natZahlen;		//deklaration und initialisation des arrays

void setBit(int j) {		//setzt das b'te bit im array -> 1
	int feld = j/32;
	int shift = 1 << j%32;
	if ((natZahlen[feld] & shift) == 0){
		natZahlen[feld] = natZahlen[feld] | shift;
	}
}
	
int getBit( int b ){	//prueft ob das b'te bit 1 ist -> true -> keine primzahl
	return natZahlen[b/32] & (1 << (b%32));
}
	
void prim(){
	int p = 2;				//start mit der ersten primzahl 2
	while ((p*p)<=n){			//waehrend das maximum der zu entfernenden zahlen (p^2) unter n ist
		int j;
		for (j=2*p; j<=n; j+=p){ //setze mehrfache von p 1 (also die nicht prim)
			setBit(j);
		}
		do { //waehrend aktive primzahl nicht n erreicht und p primzahl ist
			p++;				//erhoehe p um einz
		} while (p<=n && getBit(p));
	}
}
	
int min(int a, int b){
	return a<b? a: b;
}
	
void ausgabe(){
		int prims = 0;
		int arrayrun;
		for (arrayrun = 2; arrayrun <= n ; arrayrun ++){
			if ( getBit(arrayrun) == 0 ){ 	//!GetBit(arrayrun)
				prims = prims+1;
			}
		}
		printf("Insgesamt befinden sich %d Primzahlen in dem angegebenen Intervall\n", prims);	
		int outp = 0;
		for (arrayrun = 2; arrayrun <= n ; arrayrun ++){
			if ( getBit(arrayrun) == 0 ){ 	//!GetBit(arrayrun)
				outp++;
				printf("%d ",arrayrun);
				if (outp >=50){
					break;
				}
			}
		}
		printf("\n");
		printf("Das waren die ersten %d Primzahlen des Intervalls.\n", min(50,prims));
		int last = min(prims-50, 5);
		if (last > 0){
			printf("Es folgen die letzten %d.\n", last);
			int prims2 = 0;
			int arr[last];
			for (arrayrun = n-1; arrayrun >= 0 ; arrayrun--){
				if ( getBit(arrayrun) == 0 ){ 	//!GetBit(arrayrun)
					arr[last-prims2-1] = arrayrun;
					prims2++;
					
					if (prims2 >= last){
						break;
					}
				}
			}
			
			int i;
			for (i=0;i<last;i++){
				printf("%d ",arr[i]);
			}
		}
		printf("\n");
}


int main() {
	//n = Integer.parseInt(args[0]);	//n den startparameter zuweisen
	n = 200000000;
	natZahlen = malloc (sizeof(int) * (int)((n+1)/32+1));
	int i;
	for (i=0;i<(int)((n+1)/32+1);i++){
		natZahlen[i] = 0;
	}
	prim();
	ausgabe();
	return 0;
}