Sieve of Eratosthenes
Introduction
Sieve of Eratosthenes is an algorithm that searches for all prime numbers in the given limit. It was developed by the Greek astronomer Eratosthenes. This algorithm is very simple to compute the prime number. In the beginning, we write all the numbers between 2 and n. We mark all appropriate multiples of 2 as a composite (because 2 is the smallest prime number), and then mark all appropriate multiples of 3, and this process runs up to n.
Algorithm of Sieve of Eratosthenes
Example:
Find the all prime numbers less than the 25.
Step: 1 Write all the prime number between 2 to 25.
Step: 2 According to the algorithm we mark all appropriate multiples of 2 as a composite (because 2 is the smallest prime number and the first number of the list)
Step: 3 The next number of the list after 2 is 3, we mark all appropriate multiples of 3
Step: 4 The next number in the list after 3 is 5 which has not yet been crossed; we mark all appropriate multiples of 5
Step: 5 The next number in the list after 5 is 7 which has not yet been crossed; we mark all appropriate multiples of 7
Step: 6 This process will run until n.
Advantages of Sieve of Eratosthenes:
- It is a very efficient algorithm to filter out the prime numbers.
- Its implementation is very low.
Program
C++ language of Sieve of Eratosthenes:
Output:
Enter the number 10 Prime numbers: 2 3 5 7
Java program
Output:
Enter the number 25 List of prime numbers upto given number are : 2 3 5 7 11 13 17 19 23