FastPrepHow Many Primes Are Below n
Problems/How Many Primes Are Below n

How Many Primes Are Below n

DocuSign logoDocuSign● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A report from September 2018 describes a phone screen with two questions answered out loud, without code. This problem is based on the second one, which was about a quick method for producing the primes smaller than a number n.

The report gives no limits, output format or examples. Here you return how many primes are below n instead of the list itself, so that large n can be tested without a huge output. n goes up to 3,000,000. The editorial shows how to collect the list too. We wrote the examples.

Our version is about 75% the same as the reported question.

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) → int

Examples

Example 1

n = 20return = 8

The primes below 20 are 2, 3, 5, 7, 11, 13, 17 and 19. That is 8 primes.

Example 2

n = 3return = 1

The 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 = 10

The 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

Interview reports that mention this question

  • DocuSign SWE Intern Interviews: 27 Experiences (Part 2 of 2)

DocuSign interview experiences

  • DocuSign SWE Intern OA Questions: 53 Experiences (Part 1 of 2)
All DocuSign interview questionsSee DocuSign hiring insights
Saved
class Solution {
    public int countPrimesBelow(int n) {
        // Write your code here.
    }
}
Checking account…