Primes below a given number

Find number of prime numbers below a given number

One could test for prime, from 4 till the given number and count those numbers. This does not need extra memory but slow. Below we provide solution which is fast but needs memory. This is using Sieve of Eratosthenes method.

Approach:-

• Have a memory allocated for ints up-to given input
• Run a counter from 2 till the given number. And for each number, mark down the multiples of it as non-primes in the int array allocated (ignoring that number, i.e. x1).
• Unmarked ones are not the multiples of any number and hence primes

Solution:-

#include <iostream>
using namespace std;

int main()
{
    int input = 100;
    int *buffer =  new int[input];
    for (int i=1;i<input;i++)
        buffer[i] = 0;
    for (int i=2;i<input;i++)
    {
        int ctr = 2*i;
         while (ctr < input) {
            buffer[ctr] = 1;
            ctr+= i;
        }
    }
    cout << "Primes less than " << input << endl;
    int count = 0;
    for (int i=2;i<input;i++)
    {
        if (buffer[i] == 0) {
            cout << i << " ";
            count++;
        }
    }
    cout << "\ncount: " << count << endl;
    return 0;
}

Output:-

Primes less than 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 
count: 25