Re: prime/primes performance

[Phil Carmody <thefatphil@yahoo.co.uk>]

--- Bill Allombert <allomber@math.u-bordeaux.fr> wrote:
> > Looks like prime() is a very expensive function.  Any comment?
> 
> prime(n) read the prime difference table until it reach n. This is a
> O(n) algorithm. It would be easy to improve it to run in O(n^(1/2))
> without using much extra memory. However I am not sure this would
> be terribly useful. An implementation of the sieving formula to compute
> prime(n) for large n without computing the whole table would be much more
> interesting.

Li-bound approximation followed by a few doesn't-have-to-be-binary chops of a
prime counting function, with optional caching of some of the auxiliary phi
functions, and a sieve for the final small range would be fairly swift.

For a prime-counting function, there was a horribly bloated and noisy
discussion on sci.math which had a few diamonds in it some time about 3 years
ago - namely C source for a pretty swift algorithm that I'm sure I've taken to
well over 2^50 without it breaking into a sweat. It was by Christian Bau, I'm
sure. I can dig out a copy that I took if anyone's interested  - I'm unable to
persuade google groups to find it presently.

> Something that could be useful however would be a 2-arguments primes():
> prime(a,b) returning the vector of primes between a and b, and only
> requiring the primelimit to be > sqrt(b), using sieving.

One other thing that I'd be interested in is a nextprime/precprime which takes
a modular relation, and only returns primes satisfying that relation.
e.g. nextprime(10^12,Mod(1,49152))
Does that sound useful to anyone else? (For example Noll/Bell's 'calc' has such
a function option.)

Phil

When inserting a CD, hold down shift to stop the AutoRun feature
In the Device Manager, disable the SbcpHid device.
http://www.cs.princeton.edu/~jhalderm/cd3/


		
__________________________________ 
Do you Yahoo!? 
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/