Count the Prime Numbers

Question: Count the number of prime numbers less than a non-negative number, n.

Input : 10 

Output: 4 

Explanation: There are 4 prime numbers less than 10 - 2, 3, 5, 7 

Please refer leetcode for more info: https://leetcode.com/problems/count-primes/

Approach: 

An ancient algorithm called "Sieve of Eratosthenes" can be used here to find all prime numbers within any given limit.

Concept:

• Eliminates all composite numbers.
• We start with a number. If it is prime, then we mark all its multiples, we do this iteratively. 
• Optimization for this concept would be only to check till the square root of n. 

public int CountOfPrimes(int n)

{

//This method uses Sieve of Eratosthenes algorithm.

//We start with a number, if it is prime, then we mark

//all it's multiples. We do this iteratively.

//A little optimization would be only to check till the

//square root of n as the numbers greater than this

//will have multiples greater than n.

//An array to store if the number is composite or not.

// if the number is less than or equal 2 return 0;

//prime

if (n <= 2) return 0;

//create an array of boolean with size n.

bool[] composite = new bool[n];

//We can stop at the loop at the square root of n

for(int i = 2; i <= Math.Sqrt(n - 1); i++)

{

if (!composite[i])

{

//Multiples of i

for(int j = i * i; j < n; j += i)

{

composite[j] = true;

}

}

}

int count = 0;

for(int i = 2; i < n; i++)

{

if (!composite[i])

{

count++;

}

}

return count;

}