Join the social network of Tech Nerds, increase skill rank, get work, manage projects...

• # Sieve of Eratosthenes

• 0
• 0
• 0
• 0
• 0
• 0
• 0
• 0
• 799
Comment on it

Hello,

This blog is to help you to understand Sieve of Eratosthenes algorithm for prime number generation in easiest way. This algorithm is to calculate the prime number up to a limit with lesser time complexity, but it takes O(n) extra space  for the computation of prime numbers.

The algorithm takes all the numbers from 2 to N all initially unmarked. It starts from 2 and marks all the multiple of 2 except 2 until multiple is less then or equal to limit value. After that next number which is not marked will be selected and all the multiples of him should be marked for the given range for which multiple value is lesser then the given limit. This process is repeated until the selected number is greater then √N.

Lets take an example

Suppose we have our limit as 20, now we have to get all prime numbers up to 20.

We should take an array of size n+1 with initial value as 0 at every cell, as each array block index will represent the number and flag value(marked of unmarked) will be stored as value at that index of array.

``int[] arr = new int[n+1]``

and n = 20

The square root of 20 is 4.47 and its integer value of 4.47 is 4. So we will iterate only form 2 to 4.

Our initial array is.

``[  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]``

We take 2 as the staring point and mark all the multiples of 2 up to the limit.

``[  0,  0,  0,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1]``

Now next index value to be chosen should be marked as 0,on going one step further we found that at index 3  value is 0 so 3 is picked. And its multiples are marked.

``[  0,  0,  0,  0,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0,  1]``

4 is marked so we can't pick it. We will not go for further values as we said that we will only iterate up to square root of the limit value.

After that we left with an array whose some element are marked 1 and some 0.

``````arr   = [  0,  0,  0,  0,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0,  1]

index =   0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  20``````

Now this array will be traversed from 2 to limit value. if value at that index is unmarked (0) then that number would be prime else would be composite.

2, 3, 5, 7, 11, 13, 17 and 19 are the indexes on which values were 0 or unmarked. So these are our prime numbers up to 20.

This is a pictorial representation Sieve of Eratosthenes for limit value 100

Java Program implementing Sieve of Eratosthenes algorithm

``````import java.util.Scanner;

public class SOE {
public static void main(String[] args) {
System.out.print("Enter Your Limit Value : ");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
int[] arr = new int[n+1];
int sqrt = (int)Math.sqrt(n);
//System.out.println(sqrt);
for ( int i = 2; i <= sqrt; i++) {
if (arr[i] == 0) {
//System.out.println(" " + i);
for ( int j = 2; j <= n; j++) {
if (j*i > n)
break;
arr[i*j] = 1;
}
}
}
System.out.println("Prime number up to " + n + " are ");
for ( int i = 2 ; i < n; i++) {
if (arr[i] == 0)
System.out.print(i + " ");
}

System.out.println();
}
}
``````

And the output taking limit value as 100 will be

``````Enter Your Limit Value : 100
Prime number up to 100 are
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
``````

## 0 Comment(s)

OR
OR
Register

OR
Fill out the form below and instructions to reset your password will be emailed to you:

• Hire
• Post Projects

### Post Projects

• All at 0 Cost ....
• Post Tech Job
• Select Best Bidder
• Track the Project
• Approve Work and Pay safely
• Browse Nerds
• Work
• Find Projects Find Projects
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Manage
• Company Company

### Manage Company

• All at 0 Cost ....
• Manage Company and Employee Profiles
• Company wide Employee Productivity Reports
• Knowledge Sharing and Collaboration Tools
• Get Sales Lead and Bid for Tech Projects
• Send Invoices and Receive Payment Safely
• Learn
• Nerd Digest Nerd Digest
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Tech Q & A Tech Q & A
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General