Math Number tricks
93. Count Primes
Medium
Given an integer n, return how many prime numbers are strictly less than n.
A number is prime when it is greater than 1 and its only divisors are 1 and itself. So 2, 3, 5 and 7
are prime, while 1, 4 and 6 are not. n itself is never counted, even when it is prime.
Example 1
Input: n = 20
Output:
8Explanation: The primes below 20 are 2, 3, 5, 7, 11, 13, 17 and 19.
Example 2
Input: n = 2
Output:
0Explanation: The smallest prime is 2, and it is not less than 2.
Example 3
Input: n = 5000000
Output:
348513Check your understanding
Work out the answer for this input before you write any code.
n = 11
Constraints
0 ≤ n ≤ 5 × 106
Clarifying questions
What you would ask an interviewer before writing any code.