using System;

class SieveOfEratosthenes {
	static void Main() {
		
		Console.Write("Enter a maximum integer to check: ");
		int iMax = Int32.Parse(Console.ReadLine());
		bool[] abIsPrime = new bool[iMax + 1];
		
		// Das Array mit true initialisieren
		for (int i = 0; i <= iMax; i++) {
			abIsPrime[i] = true;
		}

		// Den Sieb-Algorithmus anwenden.
		for (int i = 2; i * i <= iMax; i++) {
			if (abIsPrime[i]) {
				for (int j = 2; j <= iMax / i; j++) {
					abIsPrime[i * j] = false;
				} // for
			} // if
		} // for

		// Die Primzahlen anzeigen
		for (int i = 2; i <= iMax; i++) {
			if (abIsPrime[i]) {
				Console.Write("{0} ", i);
			} // if
		} // for
		
	} // static void Main
} // class SieveOfEratosthenes