|Max Alekseyev on Thu, 17 May 2018 17:28:56 +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?
> Removing multiples of 2 we get
23,25,27... 2^256-1For small N, it is possible using the inclusion-exclusion principle:
> then removing multiples of 3 we get
> 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 N=3 the formula is for k = 2^256
k - (k\2) - (k\3) + (k\6)
in general we should have