http://code.activestate.com/recipes/users/4180103/2011-11-27T21:48:25-08:00ActiveState Code Recipes2011-11-27T21:48:25-08:00Sumudu Fernandohttp://code.activestate.com/recipes/users/4180103/http://code.activestate.com/recipes/577966-even-faster-prime-generator/

<p style="color: grey"> C++ recipe 577966 by <a href="/recipes/users/4180103/">Sumudu Fernando</a> (<a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/prime_generator/">prime_generator</a>). </p> <p>A very quick (segmented) sieve of Eratosthenes.</p> <p>Takes ~6s on a midrange machine to hit all 50 847 534 primes less than 1 billion, ending with 999999937</p> <p>If you want to actually <em>do</em> anything with every prime (beyond counting them), there are three places to add a statement doing whatever is necessary with "lastP" -- one at the top (handles the special case '2'), one in the middle (handles "small" primes which are actually used to sieve), and one at the bottom (handles "large" primes which merely survive sieving).</p> <p>In principle one can use a function object as parameter to allow generic operations on the primes, so add that if you want more general-purpose code (perhaps I'll do that later)</p> <p>For higher limits you need to switch to wider types and follow the commented guidelines for the constants. For a fixed limit, changing <code>B_SIZE</code> may affect performance so if needed tune it (profile as you go, of course!). But this will get quite slow if you go to much higher numbers.</p>