Count the number of Prime Numbers (LeetCode Problem-Solving—5)

The problem is to count the number of Prime Numbers which should be less than a given integer n. Prime Number: is a number which is greater than 1, that is divisible by only 1 and itself.

My articles are open for everyone; non-member readers can read the article by clicking this Friend link.

1 — Approach

To solve this problem efficiently given the constraints: 0 <= n <= 5 * 106 , the Sieve of Eratosthenes algorithm is the best approach. This algorithm helps find all prime numbers up to a given number n in O(n log log n) time.

2 — Algorithm: Sieve of Eratosthenes

1. Initialize a boolean Array:

• Create a boolean array isPrime of size n and initialize all elements to true.
• isPrime[i] will indicate whether i is a prime number.
• Set isPrime[0] and isPrime[1] to false (since 0 and 1 are not primes)

2. Mark Multiples of Primes:

• Start witht the Prime number 2. For every number p, mark all its multiples as non-prime (i.e., set isPrime[j] = false for all j = p * p, p * p + p, …, n).

Question: — Why 2 is a Prime Number, but…