1437. Far Window Primes
A researcher scans a narrow window of very large integers, from low to high inclusive, and wants to know how many of them are prime. The numbers are too large to sieve from 1, but the window is short, so only the primes up to the square root of high are needed to cross out the composites inside it. Return the count of primes in the window as an int; remember that 1 is not prime. Your solution should use a segmented sieve and run in roughly O(sqrt(high) + (high - low) log log high) time with O(sqrt(high) + (high - low)) memory.
Example 1
- Input:
- low = 1, high = 10
- Output:
- 4
- Explanation:
The primes in 1..10 are 2, 3, 5 and 7, so the count is 4.
Example 2
- Input:
- low = 90, high = 100
- Output:
- 1
- Explanation:
Only 97 is prime between 90 and 100.
Constraints
1 ≤ low ≤ high ≤ 1012
high - low ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(sqrt(high) + W log log high)
- Space
- O(sqrt(high) + W)