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

# | User | Rating |
---|---|---|

1 | tourist | 3851 |

2 | jiangly | 3634 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | ksun48 | 3493 |

6 | djq_cpp | 3486 |

7 | maroonrk | 3471 |

8 | Radewoosh | 3442 |

9 | Petr | 3426 |

10 | Isonan | 3344 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 185 |

2 | awoo | 180 |

3 | dario2994 | 171 |

4 | SecondThread | 168 |

4 | maroonrk | 168 |

4 | Um_nik | 168 |

4 | adamant | 168 |

8 | YouKn0wWho | 166 |

8 | errorgorn | 166 |

10 | antontrygubO_o | 162 |

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

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/28/2022 02:58:40 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

Thank You

I don't know much about this algorithm. Can you make a tutorial about it please ?

Yeap. Lehmer_algorithm or Efficient Prime Counting with the Meissel-Lehmer Algorithm

Updated blog link ( previous one doesn't work ) :

Efficient prime counting with the Meissel-Lehmer algorithm

If you want to enumerate all the primes upto 10^9 in 1 second,

Segment Sieve of EratosthenesplusWheel Factorizationwill help a lot.An example using primes 2, 3, 5, 7, 11, 13, code

wow...thanks a lot.

How about using

`Bitwise Segment Sieve of Eratosthenes`

. Is it better than that ?what about for 10^18?

https://codeforces.com/blog/entry/22317

Thanks a lot for giving link of this blog.

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.

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.