Prime Generation for Large Ranges

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Prime Generation for Large Ranges. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output