0

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
6
Views
6 Years
Discussion Span
Last Post by tubby123
0

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.

0

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

0

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.