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

Recommended Answers

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 …

Jump to Post

All 5 Replies

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

just went thru it, super simple.. :)

Be a part of the DaniWeb community

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