# Sum of primes below 1000000 in python, scheme, java and C, and pypy
import Euler as eu
def sum_primes_below(n):
sum = 0
i = 2
while i <= n:
if eu.miller_rabin(i):
sum +=i
i += 1
else:
i += 1
return sum
#cpython:
%time print(sum_primes_below(1000000))
37550402023 CPU times: user 16 s, sys: 0 ns, total: 16 s Wall time: 16 s
#racket scheme:
% time! racket racket_tests.rkt
37550402023 CPU times: user 248 ms, sys: 28 ms, total: 276 ms Wall time: 14 s
! touch Benchmarks.java
! javac Benchmarks.java
#java:
%timeit ! java Benchmarks
37550402023 37550402023 37550402023 37550402023 1 loop, best of 3: 5.5 s per loop
# c++:
%timeit ! ./benchmarks
375504020233755040202337550402023375504020231 loop, best of 3: 487 ms per loop
# writting pypy file
%%writefile -a benchmarks_pypy_2.py
import Euler as eu
def sum_primes_below(n):
sum = 0
i = 2
while i <= n:
if eu.miller_rabin(i):
sum +=i
i += 1
else:
i += 1
return sum
print(sum_primes_below(1000000))
Writing benchmarks_pypy_2.py
# Finally python with JIT, i.e. pypy
%timeit ! pypy benchmarks_pypy_2.py
37550402023 37550402023 37550402023 37550402023 1 loop, best of 3: 1.47 s per loop
*Results*
Taking, obviously the best, c++ as 100%:
While the firs place is not a surprise, I don't know why java is so slow comparing to pypy (I compiled file with no flags added [javac 'filename']...). All the algorithms are similar, while loop, and miller rabin test. Listings (python code above):
! cat Benchmarks.java
import java.math.BigInteger; import java.util.*; public class Benchmarks { public static long sumOfPrimes(long n) { long sum = 0; long i = 2; while (i <= n) { BigInteger tmp = new BigInteger(Long.toString(i)); if (tmp.isProbablePrime(50)) { sum += i; i += 1; } else i += 1; } return sum; } public static void main(String [] args) { //final long startTime = System.currentTimeMillis(); System.out.println(sumOfPrimes(1000000)); //final long endTime = System.currentTimeMillis(); //System.out.println("Total execution time: " + (endTime - startTime)); } }
! cat racket_tests.rkt
#lang racket (require racket/include) (include "millerrabin.rkt") (define (reduce xs f start) (if (empty? xs) start (reduce (cdr xs) f (f start (car xs))))) (reduce (filter prime? (range 2 1000000)) + 0)