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.

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     cout << "Welcome to the Sieve of Sundaram\n" << endl;
  8.     int arraySize;
  9.     int numberPrimes = 0;
  10.     cout << "Input a positive integer to find all the prime numbers up to and "
  11.             << "\nincluding that number: ";
  12.     cin >> arraySize;
  13.     int n = arraySize / 2;
  14.     /* array to start off with that will eventually get
  15.      all the composite numbers removed and the remaining
  16.      ones output to the screen                        */
  17.  
  18.     int isPrime[arraySize + 1];
  19.  
  20.     for (int i = 0; i < n; ++i)
  21.     {
  22.         isPrime[i] = i;
  23.     }
  24.  
  25.     for (int i = 1; i < n; i++)
  26.     {
  27.         for (int j = i; j <= (n - i) / (2 * i + 1); j++)
  28.         {
  29.             isPrime[i + j + 2 * i * j] = 0;/*From this list, remove all
  30.              numbers of the form i + j + 2ij    */
  31.         }
  32.     }
  33.  
  34.     int TheseArePrime = 0;
  35.  
  36.     if (arraySize > 2)
  37.     {
  38.         isPrime[TheseArePrime++] = 2;/*this IF statement adds 2 to the output     */
  39.     }
  40.  
  41.     for (int i = 1; i < n; i++)
  42.     {
  43.         if (isPrime[i] != 0)
  44.         {
  45.             isPrime[TheseArePrime++] = i * 2 + 1;
  46.         }
  47.     }
  48.  
  49.     int size = sizeof isPrime / sizeof(int);//total size of array/size of array data type
  50.  
  51.     for (int x = 0; x <= size; x++)
  52.     {
  53.         if (isPrime[x] != 0)
  54.         {
  55.             cout << isPrime[x] << "\t";//outputs all prime numbers found
  56.             numberPrimes++;// the counter of the number of primes found
  57.         }
  58.         else
  59.         {
  60.             break;
  61.         }
  62.     }
  63.  
  64.     cout << "\nNumber of Primes: " << numberPrimes << endl;
  65.     return 0;
  66. }

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.

advertisement
advertisement

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

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.