### Ahs_58's blog

By Ahs_58, history, 5 years ago,

Is there any way to find prime number upto 10^9 or more in 1 second?

• +13

 » 5 years ago, # | ← Rev. 5 →   +30 Yes. It can be easily using Meisell-Lehmer algorithm to calculate the numbers of prime up to n in O(n^{2/3}).or you can see F.Four Divisors.
•  » » 5 years ago, # ^ |   0 Thank You
•  » » 5 years ago, # ^ |   0 I don't know much about this algorithm. Can you make a tutorial about it please ?
•  » » » 5 years ago, # ^ |   +15
•  » » » » 3 years ago, # ^ |   +1 Updated blog link ( previous one doesn't work ) :Efficient prime counting with the Meissel-Lehmer algorithm
 » 5 years ago, # | ← Rev. 2 →   +8 If you want to enumerate all the primes upto 10^9 in 1 second, Segment Sieve of Eratosthenes plus Wheel Factorization will help a lot.An example using primes 2, 3, 5, 7, 11, 13, code
•  » » 5 years ago, # ^ |   0 wow...thanks a lot.
•  » » 3 years ago, # ^ |   0 How about using Bitwise Segment Sieve of Eratosthenes. Is it better than that ?
•  » » 2 years ago, # ^ |   0 what about for 10^18?
•  » » » 2 years ago, # ^ |   0
•  » » » » 8 months ago, # ^ |   0 Thanks a lot for giving link of this blog.
 » 8 months ago, # |   0 segmented seive between 2 and n will may help you to find all prime up to range 10^9.Simple seive will give u tle.
 » 6 weeks ago, # | ← Rev. 3 →   0 I checked these https://ntheory.org/sieves/benchmarks.html but even the fastest library (till 10^9) ie Kim Walisch's was not as fast as min_25's sieve. I checked zimpha's wheelsieve as well. It is quite fast as well but slightly slower than min_25. Many of the above libraies are cache efficient and thread efficient code. Which neither min_25's nor zimpha's single file code is this shows we have lot more headrooms to improve.