Hello codeforces,I'm trying to solve a problem on acmp, in this problem I only need to count the number of primes up to 10^12,do you know some algorithms to solve it?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 144 |
| 5 | Errichto | 139 |
| 6 | AmShZ | 138 |
| 7 | adamant | 137 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
Автокомментарий: текст был обновлен пользователем Vanekss (предыдущая версия, новая версия, сравнить).
Алгоритм Мейсселя-Лемера за O(n^(3/4))
I have a funny solution to this problem: split the range $$$1 \ldots 10^{12}$$$ into blocks of length $$$B$$$. Locally precompute number of primes in each block (might take some time), then you can calculate $$$\pi(n)$$$ in about $$$O(B)$$$ time.
Set $$$B$$$ somewhere between $$$10^7 \ldots 10^8 $$$ to get AC. For higher $$$B$$$ you might not have enough time to process $$$O(B)$$$ numbers and for lower $$$B$$$ you might not fit into code size limit (which is $$$2^{17}$$$ bytes on acmp).