Features
Dette er en ret hurtig implementation af Eratosthenes primtalssi.
Den finder alle primtal fra 1 til et givent tal, og angiver endvidere hvilket nummer primtallet har.
Programmet kører meget tæt på lineær tid, og min PII 266MHZ kan bestemme ca. 5 mio tal i sekundet (hvis jeg slår output fra. Det svarer til at finde alle primtal fra 1 til 1 mia på 3,5 til 4 minutter.
Programmet er ret venligt mht. hukommelse. Det tager 1 byte hukommelse for hver 16 tal man vil undersøge (dvs. at undersøgelsen af alle tal op til 1 mia fylder ca. 60 MiB i hukommelsen - til sammenligning er der 26355867 primtal i det område, altså ikke meget mere end to bytes pr. primtal).
Bemærk at disse målinger er fra en ældre udgave af programmet. Den nye og noget optimerede udgave er 50% hurtigere, og selve genereringen er tager nu kun 25% af den tid det tog tidligere (på en PIII 800 MHz tog det omkring 27 sekunder at finde alle primtal op til 100 mio (når output er slået fra, nu tager det kun 6-7 sekunder - igen med output slået fra, jeg har målt tider på kun 74 sekunder for at finde alle primtal op til 1 mia på en PIII 800Mhz - det er næsten 13 mio tal der checkes i sekundet!). Programmet bruger lige så meget hukommelse som tidligere, men er baseret på et forbedret udgave af sien.
Installation
- Hen sourcekoden her (primtal.cc, 812).
- Kompiler med gcc -O3 -m486 -o primtal primtal.cc.
- Så er du kørende!
Begrænsninger
Programmet kan ikke udregne primtal der er større end 2^31-1 (ca. 2.1 mia). Det kan ret let ændres til at køre op til 2^32 (ca. 4.2 mia). Man kan også meget let ændre det til at køre op til 2^64 (ca. 18,4 mia mia), men det ville gå ud over hastigheden.
Programmet starter fra 1. Altid. Også selvom du vil finde alle primtal mellem 1000000 og 2000000. Algoritmen tvinger det til det. det vil dog også være hurtigere (i dette tilfælde) at bruge dette program, da algoritmen er meget hurtig.
Programmet bruger meget RAM (når man når op på store tal - min computer kunne ikke lide da jeg satte den til at regne op til 2 mia for den har kun 80 MiB RAM med 256 MiB RAM fik jeg en computer gladeligt op på 2 mia).
