Count Primes Leetcode Solutions

In this problem, we are given an integer, N. The goal is to count how numbers less than N, are primes. The integer is constrained to be non-negative.

Example

7

3

10

4

Explanation

Primes less than 10 are 2, 3, 5 and 7. So, the count is 4.

Approach(Brute Force)

The general approach is to check for every integer less than N and increment the result if they are prime. For example, consider N = 10. Now, we can run a check from 2 to N - 1 to find how many primes lie in this range. But, this approach requires a prime check on the whole range, . Therefore, this is slow.

 

We can do some optimizations like:

 

- Every prime number other than 2 is an odd integer. So, after 2, we can check for odd integers only.

- We can check if a number is prime in O( √N) time to improve the algorithm.

 

However, we still have a better approach, discussed later in this article.

Algorithm

 

- If the number is less than 3, return 0, as 2 is the smallest prime

- Run a loop checking all numbers, starting from 3

- A number, N is prime if:

 

- It has 0 prime factors between 2 and √N

 

- If the number is prime, increment result

- Print the result

 

Implementation of Count Primes Leetcode Solutions

C++ Program

#include

using namespace std;

 

bool isPrime(int N)

{

for(int i = 2 ; i * i

 

www.tutorialcup.com/leetcode-solutions/count-primes-leetc...

Done