Sieve of Eratosthenes in C++
In this tutorial, we learn about sieve of Eratosthenes algorithm in C++.
Before we start, let’s know about what is sieve of Eratosthenes algorithm?
sieve of Eratosthenes algorithm is a very famous and efficient algorithm to generate all small prime numbers up to around 1-10 million. This algorithm is given by a Greek mathematician named Eratosthenes. By using this algorithm, we can write a simple program for prime number generation.
What we do in this particular algorithm is that, we first create a list of all the numbers from 2 to n and initially say that all of them are prime.
If n=25,
We create a list from 2 to 20
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20.
Now we start the first element in the list, if 2 is prime, all the multiples of 2 can’t be prime. We cancel all the multiples of 2, they are not prime because they are divided by 2.
2 3 5 7 9 11 13 15 17 19.
Now we go to 3, so all the multiples of 3 can’t be prime, so they cancel out.
2 3 5 7 11 13 17 19.
All the remaining numbers are prime. So this is how sieve of Eratosthenes algorithm works.
C++ Program: sieve of Eratosthenes in C++
#include <iostream> const int n = 20; int main() { int arr[20] = {0}; for (int i = 2; i < 20; i++) { for (int j = i * i; j < 20; j+=i) { arr[j - 1] = 1; } } for (int i = 1; i < 20; i++) { if (arr[i - 1] == 0) std::cout << i << "\t"; } }
Output: 1 2 3 5 7 11 13 17 19.
Do let me know in the comment section if you have any doubt.
Also read: How to count the number of spaces in a string in C++
Leave a Reply