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 ???
Jump to PostSieve, 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 …
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.. :)
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.