Re: nonprime(n)

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

On Tue, Feb 06, 2024 at 06:14:47PM +0100, hermann@stamm-wilbrandt.de wrote:
> On 2024-02-06 08:40, Aurel Page wrote:
> > 257M is overkill.
> > 
> > $ gp -p4M
> > ? for(n=1,2^18, prime(n));
> > time = 1,315 ms.
> > 
> > We have all the necessary primes:
> > ? prime(2^18)
> > % = 3681131
> > 
> > Cheers,
> > Aurel
> > 
> And why is forprime() so fast without -p...?
> 
> hermann@7950x:~$ gp -q
> ? c=0;forprime(p=2,oo,c+=1;if(c==2^18,print(p);break()));
> 3681131
> ? ##
>   ***   last result: cpu time 60 ms, real time 60 ms.

Compared to
? prime(2^18)
%1 = 3681131
  ***   last result computed in 5 ms.
this is not so fast.

the issue is that "for(n=1,2^18, prime(n))" does

for(n=1,2^18, c=0;forprime(p=2,oo,c+=1;if(c==n,break())))

which is a very inefficient way to do that computation.

Cheers,
Bill