How Many Primes Are Below n
Updated
Problem statement
A prime is a whole number greater than 1 whose only divisors are 1 and itself. For example, 2, 3, 5 and 7 are prime, while 1, 4 and 9 are not.
Given an integer n, return how many primes are strictly less than n. Your solution should handle the largest n quickly.
Function
countPrimesBelow(n: int) → intExamples
Example 1
n = 20return = 8The primes below 20 are 2, 3, 5, 7, 11, 13, 17 and 19. That is 8 primes.
Example 2
n = 3return = 1The numbers below 3 are 0, 1 and 2. 0 and 1 are not prime, and 2 is. The answer is 1.
Example 3
n = 31return = 10The primes below 31 are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. 31 is prime but not below 31, so the answer is 10.
Constraints
0 <= n <= 3000000
More DocuSign Phone Screen questions
- Symmetric Binary TreePHONE SCREEN · Seen Oct 2026
- Union Area of Two RectanglesPHONE SCREEN · Seen Oct 2026
- Execute Cursor-Based Text Editor OperationsPHONE SCREEN · Seen Sep 2026
- Minimize Array Sum After K Halving OperationsPHONE SCREEN · Seen Sep 2026
- Fizz and Buzz Words From 1 to nPHONE SCREEN · Seen Sep 2026
- Two Positions That Add Up to a TargetPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Rain Kept Between WallsPHONE SCREEN · Seen Mar 2026
- Exact Palindrome CheckPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Reverse the Characters of a TextPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Rebuild a Trip From Flight TicketsPHONE SCREEN · Seen Apr 2019
Similar questions at other companies
- Integers With Multiple Sum of Two CubesCharta Health · PHONE SCREEN · ONSITE INTERVIEWCharta Health interview questions
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Logistic Regression with Gradient DescentYahoo · PHONE SCREENYahoo interview questions
- Evaluate an Arithmetic Expression Written in WordsBrex · PHONE SCREEN
- Constant-Time Weighted Pick with an Alias TableEtched · PHONE SCREEN
- Integer to English Words in USD and INR StylesVeeam · PHONE SCREEN
- Adaptive Calibration ErrorOpenAI · PHONE SCREENOpenAI interview questions
- Sum of Smallest Non-DivisorsThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Square Root FunctionCitadel · PHONE SCREENCitadel interview questions
- Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions