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



Relevant Pages

  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slower with larger sieve sizes due to the large number of memory accesses. ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slows down based on size memory used ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: greatest multiple algorithm
    ... array stores found primes ... modulo with found primes in array to find new primes ... consumes large amounts of memory ... That doesn't sound like a sieve, ...
    (comp.lang.asm.x86)
  • Re: greatest multiple algorithm
    ... modulo with found primes in array to find new primes ... That doesn't sound like a sieve, ... integers upto the largest cpu supported integer type, modulo is faster on ... slower with larger sieve sizes due to the large number of memory accesses. ...
    (comp.lang.asm.x86)
  • Re: [Clax86list] Can WXP handle 4 GB of Physical Memory
    ... determine if huge chunks of memory are able to speed up a sieve ... using L1 cache. ... Since there are about TEN times as many primes between ... sieve checks for primes up to 10**18. ...
    (comp.lang.asm.x86)