PreviousNext
Coding/Bits and math

Primes in range

Write codeHard30 minCitadel style

Your task

Count the number of primes in the inclusive range [lo, hi] using a segmented sieve, where 1 <= lo <= hi <= 10^7 and hi - lo <= 10^6. The range can start high (e.g. [9999900, 10000000]) so you must NOT sieve from 0 to hi naively for the whole window; sieve base primes up to sqrt(hi) and mark only the window.

Examples

count_primes_in_range(lo: int, hi: int) -> int
Example 1
Inputcount_primes_in_range(10, 20)
Output4