Sieve of Eratosthenes

Steve of Eratosthenes is an ancient and very important algorithm for finding all primes number up to a given limit. this algorithm  is named after great Greek mathematician “Eratosthenes”.

Principle of Steve of Eratosthenes algorithm is removing all prime numbers i.e. composite numbers from array and now remaining numbers are Prime numbers. For more about algorithm go to Wikipedia.

Now without wasting your time I like discuss steps for Steve of Eratosthenes and a simple code in Java to find all prime numbers up to a limit.

Algorithm :

Step 1:

Make an array from 2 to n

[2 , 3 , 4 , 5 , 6 , 7 ,8 , 9 ,........ n]

Step 2:

Beginnings from 2 delete all of its multipliers in the array except itself.

for 2 [2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ,......n]

Step 3:

Repeat the step 2 till square root of n.

for 3 [2 ,3 , 5 , 7 ,9 , ............ n]
.
.
.
.
Repeat till sqrt(n)
Source Code

import java.util.*;
public class SteveOfEratosthenes {
    public static void main(String a[]){
        Scanner sb=new Scanner(System.in);
        int numbers;
        System.out.println("Enter the number:");
        numbers=sb.nextInt();
        int primenums[]=new int[numbers+1];
        for(int i=2;i<=numbers;i++)
            primenums[i]=i;
        int i=2;
        while((i*i)<=numbers){
            if(primenums[i]!=0){
               for(int j=2;jnumbers)
                       break;
                   else
                       primenums[primenums[i]*j]=0;
               }
            }
        i++;    
        }
        System.out.println("outPut :");
        for(i=2;i<=numbers;i++){
            if(primenums[i]!=0){
                System.out.println(primenums[i]);
            }
        }
        
    }
    
}

Output :