# Thread: Prime Time: C, Lisp, and Python

1. ## Prime Time: C, Lisp, and Python

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:
Code:
```real	0m0.312s
user	0m0.076s
sys	0m0.040s```
Lisp:
Code:
```real	0m0.996s
user	0m0.508s
sys	0m0.056s```
Python:
Code:
```real	0m0.494s
user	0m0.176s
sys	0m0.064s```
This is the code I used:
C:
Code:
```#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:
Code:
```(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:
Code:
```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:
Code:
```(save-lisp-and-die "prime-lisp" :executable t :toplevel
(lambda ()
(primes-in-range 0 100000)
(quit)))```
The C code was compiled with gcc:
Code:
`gcc -o prime-c prime.c`
The python code was interpreted normally:
Code:
`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.
Last edited by JordyD; August 8th, 2009 at 03:02 AM. Reason: Forgot to update LISP version

2. ## Re: Prime Time: C, Lisp, and Python

What are you using to benchmark them?

3. ## Re: Prime Time: C, Lisp, and Python

Originally Posted by Mirge
What are you using to benchmark them?
The 'time' command.

4. ## Re: Prime Time: C, Lisp, and Python

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.
Last edited by Can+~; July 17th, 2009 at 07:47 PM.

5. ## Re: Prime Time: C, Lisp, and Python

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:
Code:
`python -c "import filename without extension"`
That will generate the .pyc file.

6. ## Re: Prime Time: C, Lisp, and Python

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

7. 5 Cups of Ubuntu
Join Date
Mar 2009
Location
Staunton, IL
Beans
29

## Re: Prime Time: C, Lisp, and Python

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.

8. ## Re: Prime Time: C, Lisp, and Python

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'

9. ## Re: Prime Time: C, Lisp, and Python

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

10. ## Re: Prime Time: C, Lisp, and Python

Python did not improve by much:

OLD:
Code:
```real	2m37.319s
user	1m51.447s
sys	0m1.016s```
NEW:
Code:
```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.
Last edited by JordyD; July 17th, 2009 at 08:07 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•