---
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 |