Sieve Of Eratosthenes Using C++

Filed Under: C++
Sieve Of Eratosthenes Using C

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 2
Algorithm 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 Output
Sieve 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

close
Generic selectors
Exact matches only
Search in title
Search in content