# 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 <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.

        for ind from prime + reduced_prime <= ind < top by prime:

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