Member Avatar for tubby123

hey, is there an optimized way to generate primes between 2 limits ?
I was recently asked this question in an interview.

Obviously, the Brute Force method would be to run a loop between the limits and check if each number has a factot between 2 and square-root of the number.
Thats probably O(n2) + O(n) == O(n2) .

Is there an opimized way ???

  • 3 Contributors
  • 5 Replies
  • 104 Views
  • 11 Hours Discussion Span
  • Latest Post Latest Post by tubby123

Dani AI

Generated

Short answer: use a segmented sieve. As hinted, precompute primes up to sqrt(upper) and then mark multiples inside the target interval; this avoids sieving the whole [2..upper] when the range is narrow or when the upper bound is huge. 's pointer to the classic sieve is the right place to start, but a segmented approach is what interviewers expect when limits are large.

Algorithm sketch (plain steps to implement)

  1. Sieve primes up to floor(sqrt(R)).
  2. Create a boolean array for the segment [L..R], initially all true.
  3. For each small prime p, start marking multiples at max(pp, ceil(L/p)p) and mark every p steps inside the segment.
  4. Values left true and >= 2 are primes.
    Complexity and notes: pre-sieve costs about O(sqrt(R) log log sqrt(R)); marking the segment is roughly linear in the segment length plus small overhead from the primes list. Memory is O(segment_length + sqrt(R)) instead of O(R). Handle L <= 1 specially and consider storing only odds (or using a small wheel) to halve the memory/marks.

Practical Python (compact, ready to try):

def simple_sieve(limit):
    sieve = [True]*(limit+1)
    sieve[0:2] = [False, False]
    for i in range(2, int(limit**0.5)+1):
        if sieve[i]:
            for j in range(i*i, limit+1, i):
                sieve[j] = False
    return [i for i in range(2, limit+1) if sieve[i]]

def segmented_sieve(L, R):
    if R < 2: return []
    limit = int(R**0.5) + 1
    primes = simple_sieve(limit)
    seg = [True]*(R - L + 1)
    for p in primes:
        start = max(p*p, ((L + p - 1)//p)*p)
        for j in range(start, R+1, p):
            seg[j - L] = False
    return [x for i, x in enumerate(range(L, R+1)) if seg[i] and x >= 2]

When to choose alternatives: use a full sieve up to R only if R is small; use Miller–Rabin (with deterministic bases) for single very large-n primality checks.

Recommended Answers

All 5 Replies

Member Avatar for TrustyTony

Sieve, but store odd values between limits instead of 3...limit. Only you do unoptimal taking out of multiples if you take out multiples of 6 +- 1. Alternativesly prepare next_prime function which uses reasonable isprime with 2, 4, 2, 4, 2, 4 stepping for test divisors until sqrt(n) ie division test by 1/3rd of numbers in this range for 1/3rd of numbers between the limits.

But usually for big range it would make sense to do full sieve from 3 as lower boundary. or to generate at least sieve for numbers upto sqrt of upper boundary and do is_prime using primes from that smaller sieve.

Member Avatar for tubby123

hmm sir, i dint get it.
Can u explain with an example , or tell me a keyword to google ?
Sieve ??? is that a data structure ???
Sieve of Eras... ???

Member Avatar for tubby123

thanks grigg,
omg, then its a bad question to ask for an interview, i mean, its not something u can come up with in 5 mins... lol

thanks a lot for the link :),
shall go thru it

Edited by tubby123 because: n/a
Member Avatar for tubby123

just went thru it, super simple.. :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.