chandra sekaran on Thu, 17 May 2018 10:37:48 +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?


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

primepi(2^32).


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

Regards,
Chandrasekaran B


On Thu, May 17, 2018 at 1:27 PM, Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:
* chandra sekaran [2018-05-17 08:50]:
> 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.

Not sure what you mean. If you want to program this sieve in GP as stated,
it will fail: no way to store ~ 2^255 integers in memory (or disk, for that
matter).

If you want to count the primes up to N (Chebishev's \pi function ~ primepi()
in GP) using this method, this will require time O~(N) hence fail again
for the stated value [ primepi() also uses the naive O(N) method... ].

If you just want to get the value of \pi(N) for largish N, the current
best algorithm (Lagarias-Odlyzko) requires time O(N^{1/2 + epsilon}) and
tough analytic techniques but as far as I know, nobody has implemented it.
There's a much simpler combinatorial algorithm (Meissel/Lehmer/Deléglise-Rivat)
in time O(N^{2/3 + epsilon}) that has been used for all record
computations I am aware of. According to OEIS, the current record is N ~ 10^27,
still far away from your 2^256 target:

  https://oeis.org/A006880

Here's a short elementary account with (trivial) pseudocode:

  http://acganesh.com/blog/2016/12/23/prime-counting

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405
Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`



--
B.Chandrasekaran
Scientist
Regional Remote Sensing Centre (SOUTH)
RRSC-South / NRSC / ISRO / Dept.of Space
ISITE Campus,Marthahalli Outer Ring Road,
Bangalore
  Off : 080-23026044
Res : 080-42110289
Mobile:  +918660172820
              +918088506289