Prime Sieving Benchmark

Tags: Sieve
Chế độ xem rộng: –X–

Benchmark

Bảng đối chuẩn thời gian chạy các thuật toán sàng

GNU G++17 7.3.0 CF 23/9/2021

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
Select a repo