top of page

## program solution

// C++ program to print all primes smaller than or equal to n using Sieve of Eratosthenes

#include <stdio.h>
#include <string.h>
#define true  1
#define false 0

void SieveOfEratosthenes(int n)

/* Create a boolean array "prime[0..n]" and initialize all entries it as true. A value in prime[i] will finally be false if i is Not a prime, else true. */
_Bool prime[n+1];
memset(prime, true, sizeof(prime));

for (int p=2; p*p<=n; p++)
{
// If prime[p] is not changed, then it is a prime
if (prime[p] == true)
{
/* Update all multiples of p greater than or equal to the square of it numbers which are multiple of p and are less than p^2 are already been marked. */
for (int i=p*p; i<=n; i += p)
prime[i] = false;
}
}

// Print all prime numbers
for (int p=2; p<=n; p++)
if (prime[p])
printf("%d ", p);

// Driver Program to test above function
int main()

int n = 30;
printf("Following are the prime numbers smaller than or equal to %d\n",n);
SieveOfEratosthenes(n);
return 0;

## Output

Following are the prime numbers below 30

2 3 5 7 11 13 17 19 23 29

bottom of page