---
# System prepended metadata

title: Prime Sieving Benchmark
tags: [' Sieve', Benchmark, ' SPyofgame']

---

---
tags: Benchmark, Sieve, SPyofgame
---

<style>
    .markdown-body { max-width: 2000px; }
</style>

Prime Sieving Benchmark
===

###### Tags: `Sieve`

###### Chế độ xem rộng: [--X--](https://hackmd.io/4N-JNh6GToSt_wVRhREKqg?view)

-----
### Benchmark

Bảng đối chuẩn thời gian chạy các thuật toán [sàng](https://hackmd.io/@Editorial-Slayers/sieve)

[GNU G++17 7.3.0 CF 23/9/2021](https://codeforces.com/problemset/customtest)

| Num | Algorithm                                         | Time Complexity                         | $N = 10^4$ | $N = 10^5$ | $N = 10^6$ | $N = 10^7$ | $N = 10^8$ | $N = 10^9$ |
| --: | ------------------------------------------------: | :-------------------------------------- | :--------: | :--------: | :--------: |----------: | :--------: | :--------: |
|  1. | Brute-forces                                      | $O(n^2)$                                | 109ms      | 11215ms    | >15000ms   | >15000ms   | >15000ms   | MLE        |
|  2. | Trial Division                                    | $O(n\sqrt{n})$                          | 15ms       | 15ms       | 171ms      | 3993ms     | >15000ms   | MLE        |
|  3. | Improved Trial Division                           | $O(n\sqrt{n})$                          | 0ms        | 0ms        | 61ms       | 1325ms     | >15000ms   | MLE        |
|  4. | Second Improved Trial Division                    | $O\left(\frac{n\sqrt{n}}{\ln n}\right)$ | 0ms        | 0ms        | 61ms       | 1325ms     | >15000ms   | MLE        |
|  5. | Divisor Sieve                                     | $O(n\log n)$                            | 15ms       | 31ms       | 31ms       | 576ms      | 14617ms    | MLE        |
|  6. | Sundaram Sieve                                    | $O(n\log n)$                            | 15ms       | 31ms       | 31ms       | 31ms       | 1419ms     | >15000ms   |
|  7. | Eratosthenes Sieve                                | $O(n\log\log n)$                        | 0ms        | 15ms       | 15ms       | 78ms       | 1169ms     | MLE        |
|  8. | Improved Eratosthenes Sieve                       | $O(n\log\log \sqrt{n})$                 | 0ms        | 15ms       | 15ms       | 93ms       | 1014ms     | MLE        |
|  9. | Linear Eratosthenes Sieve                         | $O(n)$                                  | 0ms        | 15ms       | 15ms       | 61ms       | 795ms      | MLE        |
| 10. | Improved Linear Eratosthenes Sieve                | $O(n)$                                  | 0ms        | 0ms        | 15ms       | 77ms       | 732ms      | MLE        |
| 11. | Atkin Sieve                                       | $O(n)$                                  | 0ms        | 15ms       | 15ms       | 93ms       | 1122ms     | MLE        |
| 12. | Improved Atkin Sieve                              | $O(n)$                                  | 0ms        | 0ms        | 0ms        | 61ms       | 733ms      | MLE        |
| 13. | Non-modulo Atkin Sieve                            | $O(n)$                                  | 0ms        | 15ms       | 15ms       | 46ms       | 561ms      | MLE        |
| 14. | Improved Non-modulo Atkin Sieve                   | $O(n)$                                  | 0ms        | 0ms        | 0ms        | 46ms       | 402ms      | MLE        |
| 15. | Eratosthenes Wheel-2 Sieve                        | $O(n\log\log n)$                        | 0ms        | 0ms        | 15ms       | 62ms       | 857ms      | 9000ms     |
| 16. | Improved Eratosthenes Wheel-2 Sieve               | $O(n\log\log \sqrt{n})$                 | 0ms        | 0ms        | 0ms        | 15ms       | 546ms      | 6666ms     |
| 17. | Eratosthenes Wheel-2 Bitwise Sieve                | $O(n\log\log \sqrt{n})$                 | 0ms        | 0ms        | 0ms        | 30ms       | 234ms      | 4648ms     |
| 18. | Improved Eratosthenes Wheel-2 Bitwise Sieve       | $O(n\log\log \sqrt{n})$                 | 0ms        | 0ms        | 0ms        | 30ms       | 218ms      | 4071ms     |
| 19. | Improved Erastothenes Wheel-2-3-5-7 Sieve         | $O(n \log \log n)$                      | 0ms        | 15ms       | 15ms       | 30ms       | 358ms      | 4242ms     |
| 20. | Improved Erastothenes Wheel-2-3-5-7 Segment Sieve | $O(n \log \log n)$                      | 0ms        | 0ms        | 0ms        | 30ms       | 186ms      | 1980ms     |
| 21. | Erastothenes Segment Sieve                        | $O(n \log \log n)$                      | 0ms        | 15ms       | 31ms       | 46ms       | 312ms      | 2776ms     |
| 22. | Improved Erastothenes Segment Sieve               | $O(n \log \log n)$                      | 0ms        | 15ms       | 15ms       | 30ms       | 109ms      | 1466ms     |
| 23. | Erastothenes Segment Bitwise Sieve                | $O(n \log \log n)$                      | 0ms        | 0ms        | 0ms        | 62ms       | 546ms ?    | 5366ms ?   |
| 24. | Improved Erastothenes Segment Bitwise Sieve       | $O(n \log \log n)$                      | 0ms        | 0ms        | 0ms        | 15ms       | 46ms       | 592ms      |

