| 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? |
* 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 Not sure what you mean. If you want to program this sieve in GP as stated,
>
> 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.
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/ Talence (France) http://pari.math.u-bordeaux.
F-33405fr/ [PARI/GP]
`