tag:blogger.com,1999:blog-3824094400662352224.post8640154088531949195..comments2024-01-31T10:35:27.473-08:00Comments on BigInteger Algorithms: Primes, Sieve of EratosthenesPeterhttp://www.blogger.com/profile/17272766252412661668noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3824094400662352224.post-62613323007195543232010-12-22T02:23:32.118-08:002010-12-22T02:23:32.118-08:00Even though Sieve of Atkin in theory should be fas...Even though Sieve of Atkin in theory should be faster than Sieve of Eratosthenes your implementation of the latter is much faster than <a href="http://alicebobandmallory.com/articles/2010/01/14/prime-factorization-in-parallel#comment-5199" rel="nofollow">mine of the former</a>. I'm not surprised because I just did a naive translation from the <a href="http://en.wikipedia.org/wiki/Sieve_of_Atkin" rel="nofollow">pseudo code on Wikipedia</a> to C#.<br /><br />Peter's impl. of The Sieve Of Eratosthenes<br />n: 10000 primes: 1229 in 0 ms<br />n: 100000 primes: 9592 in 2 ms<br />n: 1000000 primes: 78498 in 20 ms<br />n: 10000000 primes: 664579 in 213 ms<br />n: 100000000 primes: 5761455 in 2744 ms<br />n: 1000000000 primes: 50847534 in 33338 ms<br /><br />My impl. of The Sieve Of Atkin<br />n: 10000 primes: 1229 in 3 ms<br />n: 100000 primes: 9592 in 6 ms<br />n: 1000000 primes: 78498 in 64 ms<br />n: 10000000 primes: 664579 in 584 ms<br />n: 100000000 primes: 5761455 in 7612 msJonas Elfströmhttps://www.blogger.com/profile/18088865137364783994noreply@blogger.com