//This is a program for printing the prime numbers
//less than a given number. The input is taken from command line.
//It uses array very effectively to solve this problem. 
//The underlying algorithm called "Sieve of Eratosthenes"
//is very simple.
//It strikes off those numbers which are multiple of 2.
//It thenstrikes off those number which are multiple of 3.
//It continues like this until it reaches sqrt(n).
//The numbers which are not striked out are the prime number.
//Try to give the reasoning.
//Try to compare it with the naive algorithm which determines
//explicitly whether each number less than n is prime.
//Try to compare on the basis of simplicity, efficiency 
//Also try to find out ways to make the following program
//more efficient.

class sieve
{
    public static void main(String args[])
    {
	int n = Integer.parseInt(args[0]);
	boolean[] A = new boolean[n+1];
	for(int i=2;i<=n;i=i+1)
	{
	    A[i] = true;
	} 

	for(int i=2;i*i<=n;i=i+1)
	{
	    for(int j=2;i*j<=n;j=j+1)
		A[i*j]=false;
	}
	
	System.out.println("The prime numbers less than "+n+" are :");

	for(int i=2;i<=n;i=i+1)
	    if(A[i]) System.out.println(i);
    }
}