# Re: finding primes

*From*: Steve O'Hara-Smith <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/

.

**Follow-Ups**:**Re: finding primes***From:*Pascal Bourguignon

**References**:**finding primes***From:*Digital Puer

- 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):