Primes Below a Limit
EasyMath & GeometryFree
Problem
A security team wants to know how many prime numbers are available as key sizes strictly below a given limit.
Return the number of primes p with p < limit.
Example 1
- Input:
- limit = 10
- Output:
- 4
The primes below 10 are 2, 3, 5 and 7.
Example 2
- Input:
- limit = 2
- Output:
- 0
2 itself is not strictly below the limit.
Example 3
- Input:
- limit = 100
- Output:
- 25
Constraints
- 0 ≤ limit ≤ 2 · 10^6
Hint
Show the first hint
Testing each number for primality by trial division repeats a lot of work.
Walkthrough
How to approach it
01Clarify before coding
- Is the limit itself included? No, strictly below: limit = 7 does not count 7.
- What about limit 0, 1 or 2? There are no primes below them; return 0.
- Is memory for one flag per number acceptable? Yes, 2 · 10^6 bytes is small.
02Brute force
For every x below the limit, try divisors up to √x and count the x with none.
Cost: O(n√n) in the worst case, around 2.8 · 10^9 steps for n = 2 · 10^6: far too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.