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

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* 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]
`