In this program, we are going to share a C++ program to print primes smaller than n using Sieve of Sundaram. If you are a beginner and want to start learning the C++ programming, then keep your close attention in this tutorial as I am going to share a program for C++ program to print primes smaller than n using Sieve of Sundaram.
Copy the below C++ program and execute it with the help of GCC compiler. At the end of this program, We have shared the output of this program.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <bits/stdc++.h> using namespace std; // Prints all prime numbers smaller int SieveOfSundaram(int n) { // In general Sieve of Sundaram, produces primes smaller // than (2*x + 2) for a number given number x. // Since we want primes smaller than n, we reduce n to half int nNew = (n-2)/2; // This array is used to separate numbers of the form i+j+2ij // from others where 1 <= i <= j bool marked[nNew + 1]; // Initalize all elements as not marked memset(marked, false, sizeof(marked)); // Main logic of Sundaram. Mark all numbers of the // form i + j + 2ij as true where 1 <= i <= j for (int i=1; i<=nNew; i++) for (int j=i; (i + j + 2*i*j) <= nNew; j++) marked[i + j + 2*i*j] = true; // Since 2 is a prime number if (n > 2) cout << 2 << " "; // Print other primes. Remaining primes are of the form // 2*i + 1 such that marked[i] is false. for (int i=1; i<=nNew; i++) if (marked[i] == false) cout << 2*i + 1 << " "; } // Driver program to test above int main(void) { int n = 20; SieveOfSundaram(n); return 0; } |
