Bill Allombert on Fri, 05 Aug 2005 14:32:46 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: addprimes() efficiency

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