Sieve Of Eratosthenes In Java

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. We will now mark all appropriate multiples of 2

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

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

5. This process will run until n. 

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

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);  
         }  
      }  
   }  
}

You can also try this code with Online Java Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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.

• What is Sieve Method?
• Sieve of Eratosthenes with Linear time complexity
• Segmented Sieve
• Prime Number Program using C
• Prime Number in Python
• Super Keyword In Java

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!