//WARNING: SLOWER THAN SIMPLE SIEVE IN PRACTICE!

/* Sieve of Eratosthenes marks some number "false" more than once
 * For example, 45 is marked false when i=3 as well as when i=5
 * With this sieve, we only mark each composite numbers false once
 * Thus this is faster
 * This is exactly 2*N. N numbers are being visited and N numbers are being marked exactly once
 * Number of primes less than or equal to N is approx N/lnN
 */
import java.io.*;
import java.util.*;
class OrderN //SLOWER IN PRACTICE, but FASTER IN THEORY
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        
        int N;
        long i,j,count=0;
        
        System.out.println("Enter N");
        N=Integer.parseInt(br.readLine().trim());
        
        long start=System.nanoTime();
        
        boolean isprime[]=new boolean[N+1];
        int prime[]=new int[N/((int)Math.log(N)-1)];
        //int SPF[]=new int[N+1]; //stores smallest prime factor of i
        
        Arrays.fill(isprime,true);
        
        isprime[0]=false;
        isprime[1]=false;
        
        for(i=2;i<=N;i++)
        {
            if(isprime[(int)i]==true)
            {
                prime[(int)(count++)]=(int)i;
                //SPF[(int)i]=(int)i;
            }
            
            for(j=0;j<count&&(i*prime[(int)j])<=N;j++)
            {
                isprime[(int)(i*prime[(int)j])]=false;
                if(i%prime[(int)j]==0)
                break;
            }
        }
        
        long end=System.nanoTime();
        
        double ans=((double)(end-start))/1000000000;
        System.out.println("\nTime taken in seconds");
        System.out.println(ans+"\n");
        
        System.out.println("Prime numbers less than N :");
        //for(i=0;i<count;i++)
        //System.out.print(prime[(int)i]+" ");
    }
}