Primes in a Window

Write count_primes_between(lo, hi) that returns how many prime numbers p have lo <= p <= hi.

The numbers can be close to a billion, but the window between them is at most 100,000 wide. Sieving every number up to a billion takes too long and too much memory, so the work has to focus on the window.

Examples

count_primes_between(1, 10)     # returns 4
count_primes_between(10, 20)    # returns 4
count_primes_between(14, 16)    # returns 0

The primes from 10 to 20 are 11, 13, 17 and 19.

Constraints

• 1 <= lo <= hi <= 10^9
• hi - lo <= 100,000