Bill Allombert on Thu, 17 May 2018 11:05:18 +0200

 Re: Prime multiples removing up to N and making list any fast method?

• To: pari-users@pari.math.u-bordeaux.fr
• Subject: Re: Prime multiples removing up to N and making list any fast method?
• From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
• Date: Thu, 17 May 2018 11:05:11 +0200
• Delivery-date: Thu, 17 May 2018 11:05:18 +0200
• Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
• References: <CAC6O5f7UdXmNQ-+WL9r+FVOAESN=6YRnjbmP=BFzc6YkZFgo3g@mail.gmail.com>
• User-agent: Mutt/1.5.23 (2014-03-12)

```On Thu, May 17, 2018 at 12:19:57PM +0530, chandra sekaran wrote:
> Is there any fast method to remove
>
> prime multiples from 1 to say 2^256 and counting the elements?
>
>  1,2,3,....2^256,
>
> Removing multiples of 2 we get
>
> 1,3,5,7,9,11,13,15,17,19,21,23,25,27... 2^256-1
>
> then  removing multiples of  3 we get
>
>  1,3,5,7,11,13,17,19,23,25,27..... 2^256
>
> then removing multiples of  5 we get
>
> 1,3,5,7,11,13,17,19,23,27,... 2^256
>
> Like this 7,11,13 up to prime N.

For small N, it is possible using the inclusion-exclusion principle:

for N=3 the formula is for k = 2^256
k - (k\2) - (k\3) + (k\6)

in general we should have

sumdiv(factorback(primes([1,N])),d,moebius(d)*(2^256\d))

Cheers,
Bill.

```