import java.io.*;

public class Prime
{
	public static void main(String[] args)
	{
		PrintWriter fileOut = createOutputFile("primes.txt");
		int x, test, counter = 3;
		System.out.print("Enter a positive integer: ");
		int upto = readInt();
		if (upto <= 0)
		{
			System.out.println(upto + " is not postive");
			System.exit(1);
		}
		long startTime = System.currentTimeMillis();
		int half = upto/2;
		if (upto >= 2)
			fileOut.println(2);
		int size = (upto-1)/2;
		boolean array[] = new boolean[size];
		while (counter <= half)
		{
			x = counter;
			fileOut.println(counter);
			while (x+counter+counter <= upto)
			{
				x += counter+counter;
				array[(x-3)/2] = true;
			}
			do
			{
				counter+=2;
			} while (array[(counter-3)/2] && counter <= half);
		}
		if ((upto&1) == 0)
			test = size/2;
		else
			test = (size-1)/2;
		for (x = test; x < size; ++x)
			if (!array[x])
				fileOut.println(x+x+3);
		System.out.println((System.currentTimeMillis()-startTime)/1000.0 + " seconds to find all prime numbers up to " + upto);
		fileOut.close();
		System.exit(0);
	}
	
	private static PrintWriter createOutputFile(String fileName)
	{
		try
		{
			return new PrintWriter(new BufferedWriter(new FileWriter(fileName)));
		}
		catch (IOException ioex)
		{
			System.out.println("Error creating output file");
			System.exit(1);
			return null;
		}	
	}
	
	private static int readInt()
	{
		BufferedReader console = new BufferedReader(new InputStreamReader(System.in));
		String s = "";
		int i = 0;
		try
		{
			s = console.readLine();
			i = Integer.parseInt(s);
		}
		catch(IOException ioex)
		{
			System.out.println("Error reading input");
			System.exit(1);
		}
		catch(NumberFormatException nfex)
		{
			System.out.println(s + " is not an integer");
			System.exit(1);
		}
		return i;
	}
}