C++ Program to Generate Prime Numbers Using Sieve of Sundaram

This is a C++ Program to generate prime numbers within a given range using Sieve of Sundaram.

Here is source code of the C++ Program to Generate Prime Numbers Between a Given Range Using the Sieve of Sundaram. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <iostream>
```
```
 
```
```
using namespace std;
```
```
 
```
```
int main()
```
```
{
```

    cout << "Welcome to the Sieve of Sundaram\n" << endl;

```
    int arraySize;
```
```
    int numberPrimes = 0;
```

    cout << "Input a positive integer to find all the prime numbers up to and "

            << "\nincluding that number: ";

```
    cin >> arraySize;
```
```
    int n = arraySize / 2;
```

    /* array to start off with that will eventually get

     all the composite numbers removed and the remaining

     ones output to the screen                        */

```
 
```
```
    int isPrime[arraySize + 1];
```
```
 
```
```
    for (int i = 0; i < n; ++i)
```
```
    {
```
```
        isPrime[i] = i;
```
```
    }
```
```
 
```
```
    for (int i = 1; i < n; i++)
```
```
    {
```

        for (int j = i; j <= (n - i) / (2 * i + 1); j++)

```
        {
```

            isPrime[i + j + 2 * i * j] = 0;/*From this list, remove all

             numbers of the form i + j + 2ij    */

```
        }
```
```
    }
```
```
 
```
```
    int TheseArePrime = 0;
```
```
 
```
```
    if (arraySize > 2)
```
```
    {
```

        isPrime[TheseArePrime++] = 2;/*this IF statement adds 2 to the output     */

```
    }
```
```
 
```
```
    for (int i = 1; i < n; i++)
```
```
    {
```
```
        if (isPrime[i] != 0)
```
```
        {
```

            isPrime[TheseArePrime++] = i * 2 + 1;

```
        }
```
```
    }
```
```
 
```

    int size = sizeof isPrime / sizeof(int);//total size of array/size of array data type

```
 
```
```
    for (int x = 0; x <= size; x++)
```
```
    {
```
```
        if (isPrime[x] != 0)
```
```
        {
```

            cout << isPrime[x] << "\t";//outputs all prime numbers found

            numberPrimes++;// the counter of the number of primes found

```
        }
```
```
        else
```
```
        {
```
```
            break;
```
```
        }
```
```
    }
```
```
 
```

    cout << "\nNumber of Primes: " << numberPrimes << endl;

```
    return 0;
```
```
}
```

Output:

$ g++ SieveOfSundaram.cpp
$ a.out
 
Welcome to the Sieve of Sundaram
 
Input a positive integer to find all the prime numbers up to and 
including that number: 10
2	3	5	7	
Number of Primes: 4
 
Welcome to the Sieve of Sundaram
 
Input a positive integer to find all the prime numbers up to and 
including that number: 100
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	
Number of Primes: 25

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

« Prev - C++ Program to Solve Linear Equation

» Next - C++ Program to Implement the Schonhage-Strassen Algorithm for Multiplication

Related Posts:

Recommended Articles: