PPractick

The problem

An online game hands out bonus rewards on "prime days": days when the player's streak count is a prime number. The server checks millions of streak values a day, and some are close to 10^9. Your task: decide whether N is prime, meaning greater than 1 with no divisors other than 1 and itself. Testing every number below N is hopeless at this scale; the √N trick from the divisors problem brings each check down to about 30,000 steps, and skipping even numbers halves that again.

Example: 17 → true, 25 → false (5 × 5), 1 → false.

Function signature

bool isPrime(long long n);  // true if n is prime

Test cases

Input n	Output	Explanation
1	false	1 is not prime by definition
2	true	The only even prime
3	true
4	false	2 × 2
17	true
25	false	5 × 5, found when i reaches √25
97	true
1000000007	true	A well-known large prime
999999937	true	The largest prime below 10^9
0	false

(Confirm: 0 ≤ n ≤ 10^9 or larger; numbers below 2 are not prime.)

How interviewers phrase it

• "Check whether N is prime."
• "Print all primes up to N" (which leads to the Sieve of Eratosthenes).
• "Count primes less than N" (LeetCode 204).

Clarifying questions to ask

1. How large can N be?
2. How many numbers need checking? One query, or many? (Many queries up to a limit suggest a sieve.)
3. How should 0, 1 and negative numbers be treated?

Follow-ups to expect

1. "Why only check up to √N?"
2. "Can you make it faster?"
3. "What if you need all primes up to 10^7?"
4. "What about numbers around 10^18?"
5. "Complexity?"

Related questions

• Count all Digits of a Number Easy
• Reverse a number Easy
• Palindrome Number Easy
• GCD of Two Numbers Easy
• Check if the Number is Armstrong Easy
• Print all Divisors Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in