Re: prime/primes performance

[Bill Allombert <allomber@math.u-bordeaux.fr>]

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.