Count Primes

Back to problems

Leetcode

Medium

Number Theory

Arrays

Google

Count Primes

Count how many prime numbers are strictly less than a given integer $n$ .

Acceptance 0%

Start Practice

Problem Statement

Given a non-negative integer $n$ , return the number of prime numbers that are strictly less than $n$ .

A prime number is an integer greater than $1 $that has exactly two positive divisors: \$ 1$ and itself.

Your task is to count all such numbers in the range $[2, n-1]$ .

Input Format

A single integer $n$ .

Output Format

Return the number of prime numbers strictly less than $n$ .

Constraints

$0 \le n$
The intended solution should be efficient for large $n$ .

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 10

Output

Explanation

The primes less than 10 are 2, 3, 5, and 7.

Example 2

Input

n = 0

Output

Explanation

There are no prime numbers less than 0.

Show 1 more example

Example 3

Input

n = 2

Output

Explanation

There are no prime numbers less than 2.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress