Prime Time: C, Lisp, and Python

[JordyD]

I created three programs, all the same functions, and used 'time' on their executables. They were written in C, Lisp, and Python. They all find all the prime numbers between 0 and 100000. I found it interesting, so I figured I'd share the results.

It's most impressive when you run them yourself.

These are their runtimes:
C:

real	0m0.312s
user	0m0.076s
sys	0m0.040s

Lisp:

real	0m0.996s
user	0m0.508s
sys	0m0.056s

Python:

real	0m0.494s
user	0m0.176s
sys	0m0.064s

This is the code I used:
C:

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool check_prime(int num)
{
	int dividend;
	double check_to = sqrt(num);

	for (dividend = 2; dividend <= check_to; dividend++) {
		if (num % dividend == 0) {
			return false;
		}
	}

	return true;
}

void primes_in_range (int from, int to)
{
	int current;

	for (current = from; current <= to; current++) {
		if (check_prime(current))
			printf("%d\n", current);
	}
}

int main()
{
	primes_in_range(0, 100000);
}

Lisp:

(proclaim '(optimize (speed 3) (safety 0) (debug 0)))
(defun check-prime (num)
  (declare (type fixnum num))
  (if (< 2 num)
      (let ((chk-to 2))
	(loop for dividend from 2 upto chk-to
	   do (when (equal (rem num dividend) 0)
		(return nil))
	   finally (return t)))
      t))
(defun primes-in-range (start stop)
  (declare (type fixnum start stop))
  (loop for current from start to stop
     do (when (check-prime current)
	  (format t "~a~%" current))))

Python:

import psyco; psyco.full()
from math import sqrt

def check_prime(num):
	dividend = 0
	check_to = int(sqrt(num)) + 1
	
	for dividend in range(2, check_to):
		if num % dividend == 0:
			return False
	return True

def primes_in_range(start, stop):
	current = 0
	
	for current in range(start, stop):
		if check_prime(current):
			print current
			
primes_in_range(0, 100000)

If you think you can make the code faster, go ahead, and I'll update the time results.

If you want to add a language, post it. I won't add it to the OP, but it would be interesting to see other languages, too.

As for the Lisp code, I created an executable by loading it into sbcl and executing:

(save-lisp-and-die "prime-lisp" :executable t :toplevel
		   (lambda ()
		   (primes-in-range 0 100000)
		   (quit)))

The C code was compiled with gcc:

gcc -o prime-c prime.c

The python code was interpreted normally:

python prime.py

The version of python used: 2.6.2

I ran these on Ubuntu 9.04 on a Dell Latitude D610.

Keep in mind that I'm very much a novice, so if you see some way to improve any of the code or anything, tell me.

Also keep in mind that these aren't very fair comparisons, considering that it's only testing one kind of function.

[Mirge]

What are you using to benchmark them?

[JordyD]

What are you using to benchmark them?

The 'time' command.

[Can+~]

Try running the python one again (do not delete the .pyc).

Also, there's a serious lag when printing the value of a variable that adds noise to your test, this affects all of them.

[nvteighen]

You're being unfair with Python... Your asking Python to bytecompile and then execute... You should have compiled it and then reinvoke Python to execute it from the .pyc to make this a fair test.

Do this:

python -c "import filename without extension"

That will generate the .pyc file.

[JordyD]

I will do that and update the python results when done.

[arcdrag]

I know algorithm efficiency isn't your goal here...but getting the first 100K primes can be done in well under a second with the right algorithm in C.

[tribaal]

Algorithmically, you should only check up to the square root of the number, not "number / 2"...
Computing the square root is a trivial operation compared to going from "square root" to "num /2", especially for large numbers.

But that affects your 3 versions, so it's still kind of valid, while artificial.

Have fun

- Trib'

[Can+~]

Also, it would be nice to see the result in Pyrex.

[JordyD]

Python did not improve by much:

OLD:

real	2m37.319s
user	1m51.447s
sys	0m1.016s

NEW:

real	2m18.495s
user	1m50.503s
sys	0m0.688s

Maybe I already compiled to bytecode earlier and forgot? I think I ran it once as a test, then ran it again with a 'time' prepended to the command.

I will now update my OP.