Loïc Grenié on Thu, 17 May 2018 10:51:31 +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 2018-05-17 at 10:37 GMT+02:00 chandra sekaran <sekar.bc@gmail.com>:
Let us have [1,2,4,.... 2^32].

If we remove all prime multiples in the above the result is

prime number list up to 2^32 and total count is


But i want remove up to first 100 primes multiples, not all the prime multiples form the

array. Any fast method or iterate over 2^32

    This should be roughly \prod_{n=1}^{100}\left(1-\frac{1}{p_n}\right)2^{32}
  (or 2^{256}) i.e. prod(n=1,100,1-1./prime(n))*2^256. I said "roughly" because
  there are rounding errors (you have to account for the last slice between two
  multiples of each p_n which is not in [1,2^{256}] which is not completely
  included in [1,2^{256}]. This should not be a problem.