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

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 …

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