Re: finding primes
 From: Steve O'HaraSmith <steveo@xxxxxxxxxx>
 Date: Fri, 27 Oct 2006 10:03:00 +0100
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/
.
 FollowUps:
 Re: finding primes
 From: Pascal Bourguignon
 Re: finding primes
 References:
 finding primes
 From: Digital Puer
 finding primes
 Prev by Date: Re: Portable use of timers
 Next by Date: Re: finding primes
 Previous by thread: finding primes
 Next by thread: Re: finding primes
 Index(es):
Relevant Pages
