Re: finding primes



On 27 Oct 2006 00:44:17 -0700
"Digital Puer" <digital_puer@xxxxxxxxxxx> wrote:

Got this on an interview question: given two integers A and B,
find all primes between them.

I basically wrote an initial function, bool isPrime(int i), which
loops over all numbers between 2 and sqrt(i) to see if i%num == 0,
in which case the number is not a prime. With this function I loop
between A and B, calling isPrime() on each value.

Is there a better way to do this? I looked at the Sieve of
Eratosthenes,
which didn't seem to be much better.

The sieve will be much faster (one run of the sieve to max(A, B)
will pick out all the primes without having to calculate the square root
of every number in the range or perform any modulus operations - both
of these are expensive), but at the cost of using memory proportional to
the largest of A and B. If time is important then the sieve is a good
approach, if memory is tightly constrained and time does not matter then
your approach is better - if the integers are very large then the sieve may
not be feasible at all (few systems have 2^64 bits of memory available).

Key lesson here - better is not a simple comparison, you have to
consider the costs and benefits and weigh them against the requirements and
constraints.

--
C:>WIN | Directable Mirror Arrays
The computer obeys and wins. | A better way to focus the sun
You lose and Bill collects. | licences available see
| http://www.sohara.org/
.