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

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

Originally Posted by ahmatti
Hi Gunksta,
Code:
```test <- rep(num, length(check))
min(test%%check)```
with:
Code:
`min(num %% check)`
That makes sense. For grins and giggles I will use this edit and think about it at work to see if I can come up with any other optimizations.

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

I jut noticed something - in the python test code you use range(). The range function in python is significantly slower than the xrange function, especially for large values of N. the use is exactly the same, just add an x. Changing this in both the places where range is used reduced the time by about 0.01 on average on my computer.

By the way, I hope you realize that on this test the only reason the python program is so close to the C one is 1) the use of psyco which makes the memory use go way up and 2) the fact that you are printing the output, which slows all of the programs down significantly.
Last edited by smartbei; July 22nd, 2009 at 08:49 PM. Reason: cleared up reasoning

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

Originally Posted by smartbei
I jut noticed something - the range function in python is significantly slower than the xrange function, especially for large values of N. the use is exactly the same, just add an x. Changing this in both the places where range is used reduced the time by about 0.01 on average on my computer.
Because range() returns a list, while xrange() an iterator object. IIRC, Python 3.0 replaces range()'s behaivor by xrange()'s and removes xrange().

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

Perl code.

Code:
```time perl -e '
use integer;
print "2\n";
for (\$i=3; \$i<=100000; \$i+=2) {
print \$i."\n" if prime(\$i);
};

sub prime {
\$n = shift;
\$sq = sqrt(\$n);
for (\$j=3;\$j<=\$sq;\$j++) {
return 0 if (\$n%\$j == 0);
}
return 1;
}
'```
Code:
```slavik@slavik-desktop:~\$ time perl -e 'use integer; print "2\n"; for (\$i=3; \$i<=100000; \$i+=2) { print \$i."\n" if prime(\$i); }; sub prime { \$n = shift; \$sq = sqrt(\$n); for (\$j=3;\$j<=\$sq;\$j++) { return 0 if (\$n%\$j == 0); } return 1; }' > /dev/null

real	0m0.483s
user	0m0.480s
sys	0m0.004s
slavik@slavik-desktop:~\$

with output (no redirect to dev null):
real	0m0.551s
user	0m0.444s
sys	0m0.048s```
edit: after some optimization:
Code:
```slavik@slavik-desktop:~\$ time perl -e 'use integer; print "2\n"; for (\$i=3; \$i<=100000; \$i+=2) { print \$i."\n" if prime(\$i); }; sub prime { \$n = shift; \$sq = sqrt(\$n); for (\$j=3;\$j<=\$sq;\$j+=2) { return 0 if (\$n%\$j == 0); } return 1; }' > /dev/null

real	0m0.326s
user	0m0.324s
sys	0m0.004s
slavik@slavik-desktop:~\$

with output:
real	0m0.363s
user	0m0.300s
sys	0m0.040s```
Hint: 2 is the only even prime.
Last edited by slavik; July 23rd, 2009 at 07:18 AM.

5. First Cup of Ubuntu
Join Date
Nov 2012
Beans
1

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

Originally Posted by ahmatti
I wrote this in R just for fun and comparison, the result from:

Code:
`R --vanilla <primes.R`
Code:
```real    0m16.612s
user    0m16.245s
sys     0m0.364s```

And the code:

Code:
```checkprime <- function(num){
dividend <- 0
checkto  <- round(sqrt(num))
for (dividend in 2:checkto){
if (num %% dividend == 0) return(FALSE)
}
return(TRUE)
}

primes_in_range <- function(start, end){
current <- 0
for (current in start:end){
if (checkprime(current) == TRUE){
print(current)
}
}
}

primes_in_range(0, 100000)```

Hi! Your code is so slow because of the print comand which make to run like a slug. In this way, putting all the prime numbers found in a vector and returning it via return(output) at the end, you can save lots of time, from 16s to around 6.5s. But the major step is in compiling the function via the "compiler" package.

Code:
```
library("compiler")

checkprime <- function(num){
checkto  <- round(sqrt(num))
for (dividend in 2:checkto){
if (num %% dividend == 0) return(FALSE)
}
return(TRUE)
}

checkprime<-cmpfun(checkprime)

primes_in_range <- function(start, end){
output  <- 0
for (current in start:end){
if (checkprime(current) == TRUE){
output <- c(output,current)
}
}
return(output)
}

primes_in_range<-cmpfun(primes_in_range)

system.time(primes_in_range(0, 100000))```
Before compiling
Code:
```
user  system elapsed
6.26    0.00    6.27```
After compiling
Code:
```
user  system elapsed
1.88    0.00    1.87```
Hope that helps!Bye!
Last edited by Nigmastar; November 9th, 2012 at 12:37 PM.