Project Euler #10 in Cython I'm trying to teach myself some Cython. To do so, I use Project Euler #10:


  The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
    2 Find the sum of all the primes below two million.


My Cython code is:

from libcpp.vector cimport vector
from libcpp cimport bool

SOLL = 142913828922

def run(unsigned long top = 2000000):

    cpdef unsigned long ist = 2
    cdef vector[bool] pos
    pos.resize(top, True)
    top //= 2

    # reduced_prime is (prime - 1)/2, since all primes (except 2) are uneven
    cpdef unsigned long reduced_prime, ind, prime

    for reduced_prime in range(1, top):
        if pos[reduced_prime]:
            prime = reduced_prime*2 + 1

            for ind in range(prime + reduced_prime, top, prime):
                pos[ind] = False

            ist += prime

    return ist


which needs about .19s to run. The following C++ code only needs .01s:

#include &lt;vector&gt;
#include &lt;iostream&gt;

int main() {
    unsigned long top = 2000000;
    unsigned long ist = 2;

    std::vector&lt;bool&gt; pos(top, 1);
    top /= 2;

    for (unsigned long reduced_prime = 1; reduced_prime &lt; top; reduced_prime++) {
        if (pos[reduced_prime]) {
            unsigned long prime = reduced_prime*2 + 1;

            for (unsigned long ind = prime + reduced_prime; ind &lt; top; ind += prime) {
                pos[ind] = 0;
            }

            ist += prime;
        }
    }

   std::cout &lt;&lt; ist &lt;&lt; std::endl;
}


Therefore I'm under the impression my Cython code is suboptimal.

For the off-chance it matters, Cython code was compiled with:


  cython src/e010.pyx -3 --cplus -o src/e010.cpp
  g++ -shared -pthread -fPIC -fwrapv -O2 -Wall -fno-strict-aliasing -I/usr/include/python3.2mu src/e010.cpp -o src/e010.so


C++ code was compiled by:


  g++ e10.cpp -O2 -o e10


Timings are taken with time on Ubuntu 12.04.
Change the inner loop to use old Pyrex syntax:

        for ind from prime + reduced_prime &lt;= ind &lt; top by prime:
            pos[ind] = False


Apparently Cython still does not optimize range loops to pure C when step size is a variable: ticket #546.