Sziasztok!
Az alábbi programot szeretném optimalizálni, (azaz nem a hardvert fejleszteni) úgy hogy gyorsabban lefusson.
$ cat prim.c
$ gcc -Wall -O3 prim.c -o prim
$ time ./prim 1000000
DB: 1000000 PRIM: 15485863
real 0m14.426s
user 0m14.125s
sys 0m0.028s
Tudom, hogy néhány módszerrel lehetne még egy-két tizedet nyerni a dolgon, de nem ilyenre vágyom.
Van ötletetek, hogyan lehetne 10s alá menni? Esetleg más matematikai módszerrel, vagy valamilyen trükkel, netalán valamit nagyon elrontok?
Előre is köszi. :)
ps: Tudom, hogy 2^31 nagyságrendű prímnél elszállna a program, de jelenleg értelmes időn belül ezt megközelíteni sem tudom.
ps2: Az esetleges bemeneti argumentumhiba szándékosan nincs lekezelve.
ps3: Félreértések elkerülése végett a célom az, hogy mondjuk a 100 000 000. prímet megtaláljam, méghozzá gyorsan. :)
[UPDATE]
Volt végre tíz percem, s mivel elmúlt a másnaposságom, gyorsan megírtam a szitás módszerrel is. Egészen meglepődtem. :)
$cat prim2.c
$ gcc -Wall -O3 prim2.c -o prim2
$ time ./prim2 15485863
DB: 1000000 PRIM: 15485863
real 0m1.730s
user 0m1.616s
sys 0m0.036s