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

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

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.