Karim Belabas on Thu, 17 May 2018 09:57: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? |
* 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] `