Primes in a Far Window
HardMath & Geometry
Problem
A lottery draws ticket numbers from the range [low, high]. The numbers can be as large as 10^12, but the range itself is at most a million numbers wide.
Return how many primes lie in [low, high] (both ends included).
Example 1
- Input:
- low = 1, high = 10
- Output:
- 4
2, 3, 5 and 7. Note that 1 is not prime.
Example 2
- Input:
- low = 10, high = 20
- Output:
- 4
11, 13, 17 and 19.
Example 3
- Input:
- low = 999999999989, high = 999999999989
- Output:
- 1
999999999989 is prime.
Constraints
- 1 ≤ low ≤ high ≤ 10^12
- high - low ≤ 10^6
Hint
Show the first hint
A full sieve up to 10^12 needs a terabyte. But any composite x ≤ 10^12 has a prime factor at most √x ≤ 10^6.
Walkthrough
How to approach it
01Clarify before coding
- Are both ends inclusive? Yes.
- Can low be 1? Yes, and 1 must not be counted as prime.
- How wide is the window? At most 10^6 + 1 numbers, so one flag per number in the window is fine.
02Brute force
Test every number in the window by trial division up to its square root.
Cost: O((high - low) · √high): about 10^6 · 10^6 = 10^12 divisions.
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.
This problem is part of Pro.