Re: forprime

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

On Mon, Sep 17, 2012 at 10:21:03PM +0200, Karim Belabas wrote:
> * Bill Allombert [2012-09-17 18:50]:
> > On Sun, Sep 16, 2012 at 09:12:14AM +0200, Karim Belabas wrote:
> > > > On Sat, Sep 15, 2012 at 3:36 AM,  <michel.marcus@free.fr> wrote:
> > > > > forprime loops over prime numbers.
> > > > >
> > > > > is there a  function that would loop over composite numbers ?
> > > * Charles Greathouse [2012-09-15 09:41]:
> > > > I typically write
> > > > 
> > > > p=3; forprime(q=5, lim, for(n=p+1, q-1, /* your code here */); p=q)
> > > 
> > > It's not easy to do this properly in GP and the result is not that readable
> > > [ N.B. the above loops through composites only up to precprime(lim) ]
> > > 
> > > I just committed a function forcomposite() to 'master', following the (new)
> > > forprime() model:
> [...]
> > What is the usecase for such function ? I never needed it myself.
> > 
> > At worse you can do 
> > for(a=1,1000,if(!isprime(a),print(a)))
> 
> Rather slower than the original code snippet, but more correct.
> 
> (20:07) gp > lim=10^8;
> (20:07) gp > s=0;forcomposite(q=3,lim,s++); s
> time = 12,846 ms.
> %2 = 94238544

If performance matter, try
my(s=0);my(old=3);forprime(p=3,lim,for(i=old+1,p-1,s++);old=p);for(i=old+1,lim,s++);s

which is basically the GP version of your C code and should be only 15% slower.

Cheers,
Bill.