11

Sieve Of Eratosthenes Using C++

 3 years ago
source link: https://www.journaldev.com/61127/sieve-of-eratosthenes-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

In this article, we will learn to implement the Sieve of Eratosthenes using C++. If you’re a competitive programmer, most probably you’d be familiar with this term. But if you’re not, sit back and relax, we’ll see in the following sections what it means and the concept behind it. This is going to be slightly challenging for newbies but we’ll try our best to help you grab the concept.

What Is Sieve Of Eratosthenes?

Suppose you want to find all the prime numbers up to a certain value say N. The Sieve of Eratosthenes is an algorithm that lets you discover all the prime numbers up to the given limit. What’s even cooler is that the time complexity of this algorithm is highly optimized for large values of N.

Consider the following examples to have better clarity

N = 10
Prime Numbers: 2, 3, 5, 7
N = 50
Prime Numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
N = 100
Prime Numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Concept – Sieve Of Eratosthenes

Instead of checking every number as prime(brute force approach), we would work on the groups. First, we will create a vector of boolean values. The rest of the work is going to be on this vector only.

Note: Integer vector could also be used but using bool values we can save on memory because we are not utilizing any integer value.

  • Create a boolean vector of size = N. Initialize the vector elements with true.
  • Next up, we will mark all the even elements as false
    • Because all the even numbers except the number 2 are non-primes.
    • To do this, we will run a for loop from i = 3 to i = N – 1
    • for(int i = 4; i < N; i += 2)
      • sieve[i] = false;
    • Notice that we are incrementing i as i += 2. This will cover all the even numbers till N.
  • Now, we will mark all the multiples of odd numbers as false.
    • for(int i = 3; i < N; i += 2)
      • To mark the multiples, we will use an optimized technique
      • Rather than starting from j = 0 and going all the way till j = N
      • we will start from j = i * i. This optimization saves us a lot of time.
      • for(int j = i * i; j < N; j += i)
        • sieve[j] = false
  • Finally, we will mark sieve[0] and sieve[1] as false and return.
  • Note: Since we are passing a vector to a function. We have to pass it by reference to save the changes.

Algorithm

void prime_sieve(vector <bool> &sieve, int N)
{
// mark address 0 and 1 ans false
// as these are not primes
sieve[0] = sieve[1] = false;
// mark all the even numbers as false
for(int i = 4; i < N; i += 2)
sieve[i] = false;
// now mark the multiples of all
// the odd numbers as false
for(int i = 3; i < N; i += 2)
for(int j = i * i; j < N; j += i)
sieve[j] = false;
}
Algorithm 2Algorithm 2

Sieve Of Eratosthenes Using C++ Program

#include <iostream>
#include <vector>
using namespace std;
void prime_sieve(vector <bool> &sieve, int N)
{
// mark address 0 and 1 ans false
// as these are not primes
sieve[0] = sieve[1] = false;
// mark all the even numbers as false
for(int i = 4; i < N; i += 2)
sieve[i] = false;
// now mark the multiples of all
// the odd numbers as false
for(int i = 3; i < N; i += 2)
for(int j = i * i; j < N; j += i)
sieve[j] = false;
}
void print_primes(vector <bool> sieve)
{
for(int i = 2; i < sieve.size(); i++)
if(sieve[i])
cout << i << ", ";
cout << endl;
}
int main()
{
cout << "Enter the size of the Sieve" << endl;
int N;
cin >> N;
vector <bool> sieve(N, true);
cout << "The Sieve of Eratosthenes is:" << endl;
prime_sieve(sieve, N);
print_primes(sieve);
return 0;
}

Output

Sieve Of Eratosthenes OutputSieve Of Eratosthenes Output

Conclusion

In this article, we learned to implement the Sieve of Eratosthenes using C++. We also generated all the prime numbers up to N = 10, 100, and 1000. We started by discussing the Sieve of Eratosthenes, later we went through the concept in detail. Finally, we coded the algorithm and a C++ program to demonstrate it. That’s all for today, thanks for reading.

Further Readings

To learn more about C++ concepts, you can check out the following articles.

https://www.journaldev.com/60732/remove-consecutive-duplicates-from-string-cpp

https://www.journaldev.com/61089/euclids-division-lemma-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK