here's a simple C program i just wrote to find the nth prime number.
On my computer it's this fast:Code:#include <stdio.h> #include <stdlib.h> #include <time.h> long *primes; int numfound; int isprime(long totest) { int i=0; for(i=0; primes[i]*primes[i]<=totest; i++) { if(totest%primes[i]==0) return 0; if(i>=numfound) return 1; } return 1; } int main(int argc, char** argv) { int tofind; long totest; time_t start, end; if(argc!=2) exit(EXIT_FAILURE); tofind=atoi(argv[1]); numfound=1; primes=malloc(sizeof(long)); primes[0]=2; totest=2; start=clock(); while(numfound<tofind) { totest++; if(isprime(totest)) { numfound++; primes=realloc(primes, numfound*sizeof(long)); primes[numfound-1]=totest; } } end=clock(); printf("prime number %d: %ld\n", numfound, totest); printf("total time: %.2f\n\n", (end-start)/(float)CLOCKS_PER_SEC); free(primes); return EXIT_SUCCESS; }
This is my computer btw:Code:╭─[/data/software/c]─[howie@howie-desktop]─[0]─[111] ╰─[:)] % ./primefinder 1000000 prime number 1000000: 15485863 total time: 7.65
How fast is your computer?Code:╭─[/data/software/c]─[howie@howie-desktop]─[0]─[112] ╰─[:)] % cat /proc/cpuinfo | grep -m1 "model name" model name : AMD Phenom(tm) II X4 965 Processor
anyway, I beat ya using a slightly more clever implementation
~> time (wget -q -O - http://www.wolframalpha.com/input/?i=prime%5B1000000%5D | grep 'Result' | sed -e 's/^.*alt="\([0-9]*\)".*$/\1/i')
15485863
real 0m1.814s
nikos-mbp-3:edprime niko$ gcc -Wall -std=c99 -O3 ed.c -o ed
nikos-mbp-3:edprime niko$ ./ed 1000000
prime number 1000000: 15485863
total time: 6.58
My algo is faster :P
time ./primes
The 1000000th prime is 15485863
real 0m6.256s
user 0m6.244s
sys 0m0.007s
System profiler says:
Processor Name: Intel Core 2 Duo
Processor Speed: 3,06 GHz
Number Of Processors: 1
Total Number Of Cores: 2
L2 Cache: 6 MB
Memory: 4 GB
Bus Speed: 1,07 GHz
And GCC:
$ gcc --version
i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5646) (dot 1)
Copyright (C) 2007 Free Software Foundation, Inc.
No no, it's just to check how fast your computer is.
More specifically the thing that takes the time here is the line
because calculating the remainder of a division takes a long time. I'm using an AMD phenom chip and it seems to have a pretty good implementation of this, but Intel looks to be a bit better.Code:if(totest%primes[i]==0) return 0;
Using fairly standard hardware you could find the remainder of dividing two 32-bit words in 32 operations. sparc architecture has an operating called mulscc to do something similar for multiplication, but it didn't used to have something similar for division. maybe they added something at some stage. if i have time today i'll write a blog post about how mulscc and divscc (i suppose it would be called that) work.
with modern intel and AMD chips everything just gets exported to the maths co-processor and no one knows how that works.
something looks wrong, but this is my output:
[avenger@avenger3 tmp]$ gcc prime.c
.&[avenger@avenger3 tmp]$ time ./a.out
real 0m0.004s
user 0m0.000s
sys 0m0.000s
[avenger@avenger3 tmp]$ gcc --version
gcc (GCC) 4.4.3
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
on a:
AMD Athlon(tm) 64 Processor 3000+ @*2.00ghz
I just copied and pasted the code from this site