Count Primes

MEDIUM

Description

Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

Constraints:

0 <= n <= 5 * 10⁶

Approaches

Checkout 3 different approaches to solve Count Primes. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

Check each number from 2 to n-1 if it's prime by testing divisibility up to the square root of the number.

Algorithm

Initialize count as 0
For each number from 2 to n-1:
- Check if the number is prime
- If prime, increment count
To check if a number is prime:
- Test divisibility from 2 to square root of the number
- If any number divides evenly, return false
- If no divisors found, return true

For each number from 2 to n-1, we check if it's prime by testing if it's divisible by any number from 2 to its square root. If no number divides it evenly, it's prime.

public int countPrimes(int n) {
    if (n <= 2) return 0;
    
    int count = 0;
    for (int num = 2; num < n; num++) {
        if (isPrime(num)) {
            count++;
        }
    }
    return count;
}

private boolean isPrime(int num) {
    for (int i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

Complexity Analysis

Time Complexity: O(n * sqrt(n))Space Complexity: O(1)

Pros and Cons

Pros:

Simple to understand and implement
Works for small inputs
Minimal space requirement

Cons:

Very inefficient for large numbers
Performs redundant calculations
Not suitable for the given constraints

Code Solutions

Checking out 5 solutions in different languages for Count Primes. Click on different languages to view the code.

public class Solution { public int CountPrimes ( int n ) { var notPrimes = new bool [ n ]; int ans = 0 ; for ( int i = 2 ; i < n ; ++ i ) { if (! notPrimes [ i ]) { ++ ans ; for ( int j = i + i ; j < n ; j += i ) { notPrimes [ j ] = true ; } } } return ans ; } }

Video Solution

Watch the video walkthrough for Count Primes

Patterns:

MathEnumerationNumber Theory

Data Structures:

Array

Companies:

Accenture |Cognizant |Intel |Tech Mahindra |