Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>If you may decide you are going to C++ to improve the speed, I ported the Python sieve to C++. The full discussion can be found here: <a href="https://stackoverflow.com/questions/5293238/porting-optimized-sieve-of-eratosthenes-from-python-to-c">Porting optimized Sieve of Eratosthenes from Python to C++</a>.</p> <p>On Intel Q6600, Ubuntu 10.10, compiled with <code>g++ -O3</code> and with N=100000000 this takes 415 ms.</p> <pre><code>#include &lt;vector&gt; #include &lt;boost/dynamic_bitset.hpp&gt; // http://vault.embedded.com/98/9802fe2.htm - integer square root unsigned short isqrt(unsigned long a) { unsigned long rem = 0; unsigned long root = 0; for (short i = 0; i &lt; 16; i++) { root &lt;&lt;= 1; rem = ((rem &lt;&lt; 2) + (a &gt;&gt; 30)); a &lt;&lt;= 2; root++; if (root &lt;= rem) { rem -= root; root++; } else root--; } return static_cast&lt;unsigned short&gt; (root &gt;&gt; 1); } // https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188 // https://stackoverflow.com/questions/5293238/porting-optimized-sieve-of-eratosthenes-from-python-to-c/5293492 template &lt;class T&gt; void primesbelow(T N, std::vector&lt;T&gt; &amp;primes) { T i, j, k, sievemax, sievemaxroot; sievemax = N/3; if ((N % 6) == 2) sievemax++; sievemaxroot = isqrt(N)/3; boost::dynamic_bitset&lt;&gt; sieve(sievemax); sieve.set(); sieve[0] = 0; for (i = 0; i &lt;= sievemaxroot; i++) { if (sieve[i]) { k = (3*i + 1) | 1; for (j = k*k/3; j &lt; sievemax; j += 2*k) sieve[j] = 0; for (j = (k*k+4*k-2*k*(i&amp;1))/3; j &lt; sievemax; j += 2*k) sieve[j] = 0; } } primes.push_back(2); primes.push_back(3); for (i = 0; i &lt; sievemax; i++) { if (sieve[i]) primes.push_back((3*i+1)|1); } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload