Bill Allombert on Thu, 31 Mar 2005 01:02:20 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: prime/primes performance |
On Fri, Mar 25, 2005 at 04:58:52PM -0500, Igor Schein wrote: > Hi, > > ? n=41561; > ? # > timer = 1 (on) > ? v=primes(n);sum(k=1,length(v),v[k]) > time = 20 ms. > 9925739634 > ? sum(k=1,n,prime(k)) > time = 1,110 ms. > 9925739634 > > 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. 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. Cheers, Bill.