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.

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

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

Start.

Create a bool array of size n+1.

Start a loop from 2 to n.

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.

Else, continue to the next iteration.

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

Stop.

Example

Letâ€™s find all the prime numbers lesser than 30.

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:

Memory Usage: The Sieve of Eratosthenes requires an array to mark or store numbers. For large ranges, this can lead to high memory consumption.

Not Ideal for Dynamic Lists: If the range of numbers is not known beforehand, the Sieve may not be the most efficient choice.

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.