The other day I met a problem that needed to count the number of primes less than n with n <= 1e10. But I only know how to use sieve to solve but it can only run with n <= 1e6. Can you help me find a better solution? thanks for help!
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 151 |
The other day I met a problem that needed to count the number of primes less than n with n <= 1e10. But I only know how to use sieve to solve but it can only run with n <= 1e6. Can you help me find a better solution? thanks for help!
Name |
---|
use segmented sieve, you can easily find videos of it on youtube
Thank your idea.This is the good sieve but this can run with n<=1e8.I think another better way to solve this problem.
there exists approximate prime counting function, which gives very accurate result for small N
I had the same curiosity a while ago, so I wrote some code to find pi(n) (which is what you need) and prime(n) (n-th prime number). You can play with N and X constants to see which gives better times. Here is the code. I used Meissel–Lehmer algorithm. You can read here and here about it. If you don't understand, don't be shy and ask me! Happy new year! :D
I don’t understand how to calculate Pi(x,a). Can you explain it to me?
In my code it's the function P(niv, n, a) which, I think, it's pretty clear how it works
I understood. Thanks you so much!
But can you explain me X in your code for what?
Yes sure. X is max i so that we calculate Pi(n, a). Increasing X, lowers initial a, but it might cause P function to take much more time. After testing, I found that X should be 6 or 7.
https://en.wikipedia.org/wiki/Meissel%E2%80%93Lehmer_algorithm