The Segmented Sieve: Primes in a Large Range

The Royal Cartographer of Prime City unrolls a massive map across the war table. Trade routes stretch across millions of miles, and the cartographer must mark every prime-numbered milestone along the way. But the map is too large to sieve all at once ÔÇö the kingdom's brass computer would run out of memory. "I need a segmented approach," the cartographer mutters, tracing a finger along the route. "We sieve the small primes first, then use them to mark composites in each segment of the route. This way, we only need memory for one segment at a time." Given a range [L, R], count the number of primes in that range. The range can be very large (up to 10^9), but the width of the range is at most 10^5. The cartographer's constraints: 2 <= L <= R <= 10^9, and R - L <= 10^5 From the cartographer's verified measurements: Input: 100 200 Output: 21 Input: 1 100 Output: 25 The trade caravans are ready to depart. Count the primes along the route, and the kingdom's merchants will travel safely through the prime-numbered milestones.