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.