C++ Program to Implement 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.

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";
    }
}

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.

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).

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++”.