fork download
copy 
  1. //WARNING: SLOWER THAN SIMPLE SIEVE IN PRACTICE!
  2.  
  3. /* Sieve of Eratosthenes marks some number "false" more than once
  4.  * For example, 45 is marked false when i=3 as well as when i=5
  5.  * With this sieve, we only mark each composite numbers false once
  6.  * Thus this is faster
  7.  * This is exactly 2*N. N numbers are being visited and N numbers are being marked exactly once
  8.  * Number of primes less than or equal to N is approx N/lnN
  9.  */
  10. import java.io.*;
  11. import java.util.*;
  12. class OrderN //SLOWER IN PRACTICE, but FASTER IN THEORY
  13. {
  14.     public static void main(String args[]) throws IOException
  15.     {
  16.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  17.  
  18.         int N;
  19.         long i,j,count=0;
  20.  
  21.         System.out.println("Enter N");
  22.         N=Integer.parseInt(br.readLine().trim());
  23.  
  24.         long start=System.nanoTime();
  25.  
  26.         boolean isprime[]=new boolean[N+1];
  27.         int prime[]=new int[N/((int)Math.log(N)-1)];
  28.         //int SPF[]=new int[N+1]; //stores smallest prime factor of i
  29.  
  30.         Arrays.fill(isprime,true);
  31.  
  32.         isprime[0]=false;
  33.         isprime[1]=false;
  34.  
  35.         for(i=2;i<=N;i++)
  36.         {
  37.             if(isprime[(int)i]==true)
  38.             {
  39.                 prime[(int)(count++)]=(int)i;
  40.                 //SPF[(int)i]=(int)i;
  41.             }
  42.  
  43.             for(j=0;j<count&&(i*prime[(int)j])<=N;j++)
  44.             {
  45.                 isprime[(int)(i*prime[(int)j])]=false;
  46.                 if(i%prime[(int)j]==0)
  47.                 break;
  48.             }
  49.         }
  50.  
  51.         long end=System.nanoTime();
  52.  
  53.         double ans=((double)(end-start))/1000000000;
  54.         System.out.println("\nTime taken in seconds");
  55.         System.out.println(ans+"\n");
  56.  
  57.         System.out.println("Prime numbers less than N :");
  58.         //for(i=0;i<count;i++)
  59.         //System.out.print(prime[(int)i]+" ");
  60.     }
  61. }
Success #stdin #stdout 0.21s 41028KB
comments (?)
stdin
copy 
10000000
stdout
copy 
Enter N

Time taken in seconds
0.150200922

Prime numbers less than N :
https://ideone.com/EAXo7j
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!