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 ???

7 Years
Discussion Span
Last Post by tubby123

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.


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... ???


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: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.