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

[Max Alekseyev <maxale@gmail.com>]

Just for the record, this is Legendre's formula:

http://mathworld.wolfram.com/LegendresFormula.html

Regards,

Max

On Thu, May 17, 2018 at 5:05 AM, Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

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.