|Bill Allombert on Thu, 17 May 2018 11:05:18 +0200|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Prime multiples removing up to N and making list any fast method?|
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.