Project Euler #10 in Cython

Question

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 <vector>
#include <iostream>

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

    std::vector<bool> pos(top, 1);
    top /= 2;

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

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

            ist += prime;
        }
    }

   std::cout << ist << 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.

Answer 1

Change the inner loop to use old Pyrex syntax:

        for ind from prime + reduced_prime <= ind < 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.