The Prime Oracle: Count Primes in a Range of One Million Numbers

High in the tower of Prime City stands the Prime Oracle ÔÇö an ancient artifact that can count primes across vast distances. But the Oracle's power is limited: it can only see one million numbers at a time, though those numbers can be anywhere in the infinite number line. The kingdom's cartographers need prime counts for remote regions to map safe trade routes. The Oracle's keeper hands you a crystal lens. "Point it at any range [L, R] where R can be astronomically large ÔÇö up to a trillion ÔÇö but the range itself must be at most one million numbers wide. The Oracle will count every prime within that window." Given a range [L, R], count the number of prime numbers in that range (inclusive). Use a segmented sieve to handle the potentially enormous values of L and R while only sieving within the window. The Oracle's constraints: 2 <= L <= R <= 10^12, and R - L <= 10^6 From the Oracle's crystal records: Input: 1 10 Output: 4 Input: 10 20 Output: 1 The crystal lens hums with power. The cartographers await your count. Master the segmented sieve, and the trade routes of Prime City will be safe forever.