Re: addprimes() efficiency

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

On Tue, Aug 02, 2005 at 12:22:19PM -0400, Igor Schein wrote:
> 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:

We probably need two arrays: one for true primes and another for
'assumed' primes. That would solve this problems (no need to compute gcd
between true prime) and fix some semantic problem with addprime() and
euler().

Cheers,
Bill