Matthew van Eerde's web log
I am a Software Development Engineer in Test working for the Windows Sound team. You can contact me via email: mateer at microsoft dot com
Friend key: 28904932216450_59cd9d55374be03d8167d37c8ff4196b
When solving Project Euler problems I frequently need to iterate over prime numbers less than a given n. A Sieve of Eratosthenes method quickly and easily finds the small prime numbers; there are more complicated methods that find larger prime numbers, but with a couple of tweaks the Sieve of Eratosthenes can get quite high.
A naive implementation for finding the set of primes below n will:
There are a handful of simple optimizations that can be made to this naive implementation:
With these optimizations I can enumerate primes from 2 up to 5 billion (5 * 109) in about seven minutes. Source and binaries attached.
>primes 5000000000 Will enumerate primes <= 5000000000 = 5e+009 Memory for sieve: 298.023 MB Initialization complete: 983 milliseconds since start Sieving to 70711 Sieving complete: 4.70292 minutes since start Picking up the rest to 5000000000 Pickup complete: 6.12252 minutes since start Primes: 234954223 1: 2 23495423: 442876981 46990845: 920233121 70486267: 1410555607 93981689: 1909272503 117477111: 2414236949 140972533: 2924158169 164467955: 3438252577 187963377: 3955819157 211458799: 4476550979 234954221: 4999999883 Enumerating complete: 7.43683 minutes since start Freeing CPrimes object
There are more complicated sieves like the Sieve of Atkin which perform better but at the cost of being much more complex. So far I haven't had to resort to any of those.
EDIT September 28 2015: moved source to https://github.com/mvaneerde/blog/tree/master/primes