public class Primzahlen{
	
	static int n=0;
	static int[] natZahlen;		//deklaration und initialisation des arrays

	public static 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;
		}
	}
	
	public static int getBit( int b ){	//prueft ob das b'te bit 1 ist -> true -> keine primzahl
		return natZahlen[b/32] & (1 << (b%32));
	}
	
	public static void main(String args[]) {
		n = Integer.parseInt(args[0]);	//n den startparameter zuweisen
		long t = System.nanoTime();
		natZahlen = new int[(int)Math.ceil(n/32+1)];
		prim();
		ausgabe();
		System.err.println( (System.nanoTime()-t)/1000000000.);
	}
	
	public static 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
			for (int 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)!=0);
		}
	}
	
	public static void ausgabe(){
		int prims = 0;
		for (int arrayrun = 2; arrayrun <= n ; arrayrun ++){
			if ( getBit(arrayrun) == 0 ){ 	//!GetBit(arrayrun)
				prims = prims+1;
			}
		}
		System.out.println("Insgesamt befinden sich "+prims+" Primzahlen in dem angegebenen Intervall");	
		int outp = 0;
		for (int arrayrun = 2; arrayrun <= n ; arrayrun ++){
			if ( getBit(arrayrun) == 0 ){ 	//!GetBit(arrayrun)
				outp++;
				System.out.print(arrayrun+" ");
				if (outp >=50){
					break;
				}
			}
		}
		System.out.println();
		System.out.println("Das waren die ersten "+Math.min(50,prims)+" Primzahlen des Intervalls.");
		int last = Math.min(prims-50, 5);
		if (last > 0){
			System.out.println("Es folgen die letzten "+last+".");		
			int prims2 = 0;
			int arr[] = new int[last];
			for (int arrayrun = n-1; arrayrun >= 0 ; arrayrun--){
				if ( getBit(arrayrun) == 0 ){ 	//!GetBit(arrayrun)
					arr[last-prims2-1] = arrayrun;
					prims2++;
					
					if (prims2 >= last){
						break;
					}
				}
			}
			
			for (int i=0;i<last;i++){
				System.out.print(arr[i]+" ");
			}
		}
		System.out.println();
	}
}