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.