Re: addprimes() efficiency

[Igor Schein <igor@txc.com>]

On Sun, Apr 17, 2005 at 01:01:39PM +0200, Jeroen Demeyer wrote:
> Hello,
> 
> Is there a way in GP to add "raw" primes to the prime table?  The 
> problem is that addprimes() scales as O(n^2) where n=number of primes.
> When adding 10000 primes this really is a problem.
> 
> Maybe addprimes() should have a flag, saying "all my primes are really 
> prime, unique and sorted".

I second that request.  Here's a little illustration:

? gettime;while(1,addprimes(primes(5000));print(gettime))
2600
5260
5270
5280
5270

  *** addprimes: user interrupt after 27,000 ms.

The very first iteration is twice as fast as the subsequent ones.

Thanks

Igor