Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the Sieve of Eratosthenes?
3.
Algorithm
4.
Example
5.
 
6.
Implementation in Java  
6.1.
Java
7.
Implementation in C++
7.1.
C++
8.
Implementation in Python
8.1.
Python
9.
Limitations of Sieve of Eratosthenes
10.
Advantages of Sieve of Eratosthenes
11.
Frequently Asked Questions
11.1.
How fast is the sieve of eratosthenes?
11.2.
How can you improve the sieve of eratosthenes?
11.3.
How does the sieve of eratosthenes work?
11.4.
What is the time complexity of the sieve of eratosthenes?
11.5.
How efficient is the Sieve of Eratosthenes?
12.
Conclusion
Last Updated: Mar 27, 2024
Easy

Sieve Of Eratosthenes In Java

Author Akshat
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

The Sieve of Eratosthenes is a method for finding prime numbers. It's a simple technique created by the ancient Greek mathematician Eratosthenes in the 2nd century BC. This sieve efficiently identifies prime numbers.

Sieve Of Eratosthenes In Java

In this article, we will discuss the Sieve of Eratosthenes in java.

Also See, Multithreading in java

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes algorithm looks for all prime numbers inside the specified range. The Greek astronomer Eratosthenes invented it. To calculate a prime number, use this easy algorithm. We start by writing down all the numbers between 2 and n. Since 2 is the smallest prime number, all appropriate multiples of 2 are marked as composites, followed by all appropriate multiples of 3, and so on up to n.

Problem Statement - Given an integer N, find all prime numbers less than or equal to N.

Sample Input - 20

Sample Output - [2, 3, 5, 7, 11, 13, 17, 19]

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

  1. Start.
  2. Create a bool array of size n+1.
  3. Start a loop from 2 to n.
  4. If the element is marked, begin a loop starting from the current element's next multiple to n and mark all the numbers that are multiples of the current number before unmarking them all.
  5. Else, continue to the next iteration.
  6. Print every number that is still highlighted because it is a prime number.
  7. Stop.

Example

Let’s find all the prime numbers lesser than 30.

  1. Write all the prime numbers between 2 to 24
[2,  3,  4,  5,  6,  7,  8,  9,  10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  20,  21,  22,  23,  24]

2. We will now mark all appropriate multiples of 2

[2,  3,  4,  5,  6,  7,  8,  9,  10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  20,  21,  22,  23,  24]

3. Now the next number which is not highlighted is 3. So, we will mark all multiples of 3

[2,  3,  4,  5,  6,  7,  8910,  11,  12,  13,  141516,  17,  18,  19,  202122,  23,  24]

4. Now the next number which is not highlighted is 5. So, we will mark all multiples of 5

[2,  3,  4,  5,  6,  7,  8910,  11,  12,  13,  141516,  17,  18,  19,  202122,  23,  24]

5. This process will run until n. 

[2,  3,  4,  5,  6,  7,  8910,  11,  12,  13,  141516,  17,  18,  19,  202122,  23,  24]

6. Print every number that is still highlighted because it is a prime number.

[2,  3,  5,  7,  11,  13,  17,  19,  23]

 

 

Implementation in Java  

  • Java

Java

import java.util.Scanner;  

public class SieveOfEratosthenes  { 
  public static void main(String args[]) {  
     int N = 24; 
     boolean[] sieve = new boolean[N]; 
     
     for (int i = 0; i< sieve.length; i++) { 
        sieve[i] = true; 
     } 
     for (int i = 2; i< Math.sqrt(N); i++) { 
        if(sieve[i] == true) { 
           for(int j = (i*i); j<N; j = j+i) { 
              sieve[j] = false; 
           } 
        } 
     } 
     System.out.println("List of all prime numbers up to 24 are: "); 
     for (int i = 2; i< sieve.length; i++) { 
        if(sieve[i]==true) { 
           System.out.println(i); 
        } 
     } 
  } 
}

Output:

List of all prime numbers up to 24 are: 
2
3
5
7
11
13
17
19
23


Try it on Online Java Compiler.

Implementation in C++

  • C++

C++

#include <bits/stdc++.h>
using namespace std;

void SieveOfEratosthenes(int n)
{
   bool sieve[n + 1];
   memset(sieve, true, sizeof(sieve ));

   for (int i = 2; i * i <= n; i++) {
       if (sieve[i] == true) {
              for (int j = i * i; j <= n; j += i)
               sieve[j] = false;
       }
   }

   for (int i = 2; i <= n; i++)
       if (sieve[i])
           cout << i << endl;
}

int main()
{
   int n = 24;
   cout << "List of all prime numbers up to 24 are:"<<endl;
   SieveOfEratosthenes(n);
   return 0;
}

Output:

List of all prime numbers up to 24 are: 
2
3
5
7
11
13
17
19
23

Implementation in Python

  • Python

Python

def SieveOfEratosthenes(n):
   sieve = [True for i in range(n+1)]
   i = 2
   while (i * i <= n):
       if (sieve[i] == True):
           for j in range(i * i, n+1, i):
               sieve[j] = False
       i += 1

   for i in range(2, n+1):
       if sieve[i]:
           print(i)


if __name__ == '__main__':
   n = 24
   print("List of all prime numbers up to 24 are :"),
   SieveOfEratosthenes(n)

Output:

List of all prime numbers up to 24 are: 
2
3
5
7
11
13
17
19
23

 

We hope you have understood everything about Sieve of Eratosthenes. 🙌

Limitations of Sieve of Eratosthenes

The limitations of the Sieve of Eratosthenes are:

  1. Memory Usage: The Sieve of Eratosthenes requires an array to mark or store numbers. For large ranges, this can lead to high memory consumption.
  2. Not Ideal for Dynamic Lists: If the range of numbers is not known beforehand, the Sieve may not be the most efficient choice.
  3. Not Suitable for Large Prime Testing: While efficient for finding primes in a range, it becomes impractical for checking the primality of a single large number.

Advantages of Sieve of Eratosthenes

The advantages of the Sieve of Eratosthenes are:

  • Efficiency: It's highly efficient for finding all primes in a specified range.
  • Deterministic: The algorithm guarantees correctness, providing a deterministic way to identify primes.
  • Simple Implementation: The algorithm's logic is straightforward, making it easy to understand and implement.
  • Parallelization: It can be parallelized effectively, improving performance for large ranges of modern hardware.

Frequently Asked Questions

How fast is the sieve of eratosthenes?

Because it can readily store prime numbers up to the 1e7 range, it is incredibly quick.

How can you improve the sieve of eratosthenes?

By converting the sieve to an iterative sieve, we may further enhance the sieve to O(n).

How does the sieve of eratosthenes work?

It operates according to the cancellation of prime factors principle.

What is the time complexity of the sieve of eratosthenes?

O(nlog(log(n))) is the time complexity of the sieve of Eratosthenes.

How efficient is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is known for its efficiency in finding all prime numbers up to a given limit n. Its time complexity is O(nloglogn), making it one of the fastest algorithms for generating primes within a specified range. 

Conclusion

In the article Sieve of Eratosthenes in Java, we started our discussion with the introduction of Sieve of Eratosthenes. Further continued our conversation with Algorithm, example, and Program in Java at the end. You can refer to similar articles for further information.

 

You can refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy learning Ninja!

Previous article
Upcasting and Downcasting in Java
Next article
Difference Between this and super Keyword in Java
Live masterclass