Phil Carmody on Thu, 31 Mar 2005 13:43:18 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: prime/primes performance |
--- 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/