C++ Program to Implement Sieve of Eratosthenes

What is Sieve of Eratosthenes?

The Sieve of Eratosthenes in C++ is a method to find prime numbers. It makes a list of numbers and eliminates multiples of each prime number, leaving only the prime numbers behind. It’s an efficient way to find primes.

Example:
Let’s use the Sieve of Eratosthenes to find prime numbers up to 10:

  • Step 1: List the numbers from 2 to 10: 2, 3, 4, 5, 6, 7, 8, 9, 10.
  • Step 2: Start with 2, the first number in the list; it’s a prime number. Eliminate all multiples of 2 (except 2 itself) from the list: 4, 6, 8, 10.
  • Step 3: Move to 3, another prime number. Eliminate all multiples of 3 (except 3 itself) from the list: 6, 9.
  • Step 4: Skip 4 as it’s already marked as a multiple of 2.
  • Step 5: Move to 5, a prime number. Eliminate all multiples of 5 (except 5 itself) from the list: 10.
  • Step 6: Skip 6 as it’s already marked as a multiple of 2 and 3.
  • Step 7: Move to 7, a prime number. The process ends as there are no more unmarked numbers greater than 7.
  • Step 8: The prime numbers up to 10 are: 2, 3, 5, 7.
Implementation of Sieve of Eratosthenes in C++.

Here is the source code of the C++ Program to Implement Sieve of Eratosthenes. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C++ Program to implement Sieve of Eratosthenes
 */
 
#include <iostream>
const int len = 100;
 
int main()
{
    int arr[100] = {0};
 
    for (int i = 2; i < 100; i++)
    {
        for (int j = i * i; j < 100; j+=i)
        {
            arr[j - 1] = 1;
        }
    }
    for (int i = 1; i < 100; i++)
    {
        if (arr[i - 1] == 0)
            std::cout << i << "\t";
    }
}
Program Explanation

1. The program uses the Sieve of Eratosthenes algorithm to find prime numbers up to 100.
2. It initializes an integer array arr of size 100 with all elements set to 0.
3. The first loop (for i from 2 to 99) marks the multiples of each number i as non-prime in the array arr.
4. The second loop prints the numbers that have not been marked as non-prime (prime numbers) in the array. These are the prime numbers up to 100.
5. The program outputs the prime numbers separated by tabs.

Time Complexity: O(n * log(log n))
The Sieve of Eratosthenes algorithm has a time complexity of O(n * log(log n)) for finding all prime numbers up to n.

advertisement
advertisement

Space Complexity: O(n)
The program uses an integer array of size 100 to mark prime and non-prime numbers. Therefore, the space complexity is O(n) since the size of the array is directly proportional to the input limit (100 in this case).

Program Output
1       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

To practice programs on every topic in C++, please visit “Programming Examples in C++”, “Data Structures in C++” and “Algorithms in C++”.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.