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!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3741 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3442 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | atcoder_official | 162 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | nor | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.12.2024 08:56:56 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
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