Prime Generation for Large Ranges | Dataford Interview Questions

Bidgely's energy analytics may need to inspect large numeric ranges while identifying prime-sized intervals for internal computation. Given two integers A and B, return every prime number in the inclusive range [A, B] without allocating an array proportional to B.

Use a segmented sieve. First generate all primes up to floor(sqrt(B)), then use them to mark composite values inside the requested range.

Formal Specification

Implement primes_between(A, B), where A and B are non-negative integers and A <= B. Return a list of integers in strictly increasing order containing exactly the primes p such that A <= p <= B.

Constraints

0 <= A <= B <= 10^12
1 <= B - A + 1 <= 10^6
Return primes in strictly increasing order
Use memory proportional to the range width and sqrt(B), not to B
Do not independently trial-divide every candidate through sqrt(candidate)

Function Signature

def primes_between(A, B):

Your question is Prime Generation for Large Ranges. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem