A different take on finding primes

[Dave Angel]

Vincent Davis wrote:
> Out of pure curiosity I would like to compare the efficiency of different
> methods of finding primes (need not be consecutive). Let me be clear, given
> 2min, how many primes can you find, they need not be in order or
> consecutive. I have not seen any examples of this. I am assume the solution
> is different depending on the time give,  2min or 2 hours. I assume a sieve
> solution would be best for larger times. When the numbers get really large
> checking to see if they are a prime gets costly.
> So what do you think?
>
>   *Vincent Davis
> 720-301-3003 *
> vincent at vincentdavis.net
>  my blog <http://vincentdavis.net> |
> LinkedIn<http://www.linkedin.com/in/vincentdavis>
>
>   
The sieve can be very efficiently written, but you have to decide 
whether to optimize for memory size or for speed.  At a minimum for size 
you need an object for each prime currently found, and you will be 
looking through that list for each new candidate.  Incidentally this 
approach can be done without any division.  If you have memory to burn, 
you make a bit array equal in size to the largest prime you expect to 
encounter.

There are also good algorithms for deciding whether a number of a 
particular form is prime.  For example, there's a test for numbers of 
the form 2**n + 1.

And don't forget the Miller-Rabin test.

DaveA