---

Hvad er den mest effektive algoritme til at generere en liste af samtlige
primtal gående fra 2 til x?

Jeg er kommet frem til følgende, men måske findes der en mere effektiv måde:

1. Lad x = 2 være det første primtal
2. Lad x stige med 1 og undersøg om x er et primtal:
3. Hvis x modulus 2 = 0 så er x ikke et primtal, og gå da til pkt. 2
4. Lad y gå fra 3 til kvadratroden af x oprundet til nærmeste hele tal
5. Hvis der findes et y, hvor x modulus y = 0, er x ikke et primtal, og gå
da til pkt. 2
6. Hvis der ikke findes et y, hvor x modulus y = 0, er x et primtal, og gå
da til pkt. 2

---

Søren Hansen skrev:

>Hvad er den mest effektive algoritme til at generere en liste af samtlige
>primtal gående fra 2 til x?

Hastighedsoptimeret:

Lav et array med en boolesk variabel for hvert ulige tal op til N
(dog ikke 1). Sæt dem til sand.
Sæt nr = 1.
Gentag:
   Find næste sande element, array[nr].
   t = nr*2+1
   Sæt hvert t. element til false
   (dog ikke det aktuelle).
indtil nr==N.
For alle elementerne: hvis array[nr] er sand, så udskriv nr*2+1.


Hukommelsesoptimeret:

Beregn primtallene løbende og gem dem i et array.
Beregningen foretages ved kun at dividere en kandidat med de
fundne primtal op til Sqrt(kandidat).

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

[Søren Hansen]

| Hvad er den mest effektive algoritme til at generere en liste af
| samtlige primtal gående fra 2 til x?

Still tallene 2,3,...,x opp i en rekke.

1. Det minste gjenværende tall, a, er et primtall.
2. Fjern alle multipler av a fra rekken.
3. Gå til 1.

Ingen divisjoner, og knapt nok multiplikasjoner (å finne alle
multipler av a kan best gjøres ved gjentatt addisjon).
--
Stein Arild Strømme Tel: (+47) 2212 2521
Centre for Advanced Study Fax: (+47) 2212 2501
Drammensveien 78 <mailto:stromme@mi.uib.no>
N-0271 Oslo, Norway <http://www.mi.uib.no/~stromme>

---

Stein A Stromme <stromme@mi.uib.no> writes:

> Ingen divisjoner, og knapt nok multiplikasjoner (å finne alle
> multipler av a kan best gjøres ved gjentatt addisjon).

Tilgengæld har den en ret dårlig køretid.

--
Peter Makholm | I have no caps-lock but I must scream...
peter@makholm.net | -- Greg
http://hacking.dk |

---

Peter Makholm <peter@makholm.net> writes:

> Stein A Stromme <stromme@mi.uib.no> writes:
>
>> Ingen divisjoner, og knapt nok multiplikasjoner (å finne alle
>> multipler av a kan best gjøres ved gjentatt addisjon).
>
> Tilgengæld har den en ret dårlig køretid.

[Leder efter et sæt gamle rapporter]

Hvor hurtigt kører Eratostenes? O(n²)

Hvis vi ser på det teoretisk, så er det let at gøre i liniær
tid. Spørgsmålet er bare om det kan betale sig. Følgende stykke kode
køre i liniær tid:

vector<bool>* prime_table::sieve(prime_table::size_type s) {
vector<bool>* result = new vector<bool>(s,0);
vector<int> LPF = vector<int>(s,0);
size_type n = 2;
LPF[2] = 2;
do {
n++;
if (n % 2 == 0) {
LPF[n] = 2;
}
if (LPF[n] == 0) {
(*result)[n/2] = 1;
LPF[n] = n;
} else {
int p = LPF[n];
int f = n/p;
if ( p < LPF[f] ) {
int r = p;
if (r == 2) r--; // hack
do { r +=2; } while (!(*result)[r/2]);
if (r*f < s) LPF[r*f] = r;
}
}
} while (n <= s);
return result;
}

Men i den tilhørende rapport lykkedes det mig tilsyneladende ikke at
prøve med et så stort datasæt at den var hurtigere end en tilsvarende
implementation af en lettere optimeret Eratosthenes.

(Pladsforbruget er noget større end Erathostenes si, men kun med en
konstant faktor)

--
Peter Makholm | Perhaps that late-night surfing is not such a
peter@makholm.net | waste of time after all: it is just the web
http://hacking.dk | dreaming
| -- Tim Berners-Lee

---

Peter Makholm <peter@makholm.net> writes:

> Hvor hurtigt kører Eratostenes? O(n²)

Nej. Dette tal forudsætter, at der er O(n) gennemløb, der tager O(n)
tid, men:

1) Du behøver ikke lave flere gennemløb (udover
udskrivningsgennemløbet) når du når op til sqrt(n).

2) Chancen for at et tal m er et primtal er ca. O(1/log(m)).

3) Tiden for et gennemløb med primtallet p er O(n/p).

Det giver altså følgende approximation for køretiden:


sqrt(n)
/
| n/(log(i)*i) = n*log(log(sqrt(n)))
/
i=0

Vi har altså køretiden er O(n*log(log(sqrt(n)))), hvilket er
betydeligt mindre end O(n^2).

   Torben Mogensen (torbenm@diku.dk)

---

torbenm@pc-032.diku.dk (Torben Ægidius Mogensen) writes:

> Vi har altså køretiden er O(n*log(log(sqrt(n)))), hvilket er
> betydeligt mindre end O(n^2).

Bara ett rent estetiskt påpekande: eftersom
O(n*log(log(sqrt(n)))) är detsamma som O(n*log(log(n))) är
det enklare uttrycket att föredra.

---

Peter Makholm <peter@makholm.net> writes:

> Men i den tilhørende rapport lykkedes det mig tilsyneladende ikke at
> prøve med et så stort datasæt at den var hurtigere end en tilsvarende
> implementation af en lettere optimeret Eratosthenes.

Hmmmm, det var ikke det kode der var i rapporten, men ser det ikke
rigtig nok ud. Jeg har også koden som jeg fik godkendt.

--
Peter Makholm | I congratulate you. Happy goldfish bowl to you, to
peter@makholm.net | me, to everyone, and may each of you fry in hell
http://hacking.dk | forever
| -- The Dead Past

---

"Søren Hansen" <jes-s@mail1.stofanet.dk> writes:

> Hvad er den mest effektive algoritme til at generere en liste af samtlige
> primtal gående fra 2 til x?
>
> Jeg er kommet frem til følgende, men måske findes der en mere effektiv måde:
>
> 1. Lad x = 2 være det første primtal
> 2. Lad x stige med 1 og undersøg om x er et primtal:
> 3. Hvis x modulus 2 = 0 så er x ikke et primtal, og gå da til pkt. 2
> 4. Lad y gå fra 3 til kvadratroden af x oprundet til nærmeste hele tal
> 5. Hvis der findes et y, hvor x modulus y = 0, er x ikke et primtal, og gå
> da til pkt. 2
> 6. Hvis der ikke findes et y, hvor x modulus y = 0, er x et primtal, og gå
> da til pkt. 2

Hvis du ellers må have lister i din definition af en algoritme, så vil
jeg tro at følgende er mere effektivt:

1. Lav en liste af alle heltal fra 2 til x
2. Lad i=1 og p_i=2.
3. Fjern alle tal på formen 2*n, n>1 fra listen.
4. Lad i=i+1 og lad p_i være det næste tal i listen. Hvis ikke dette
findes, så stop.
5. Gå til 3.

Fordelen ved denne algoritme er, at du ikke behøver st undersøge om
alle tal mellem 2 og 16 dividerer 256, da dette bliver sorteret fra
til at begynde med. Metoden her er Eratosthenes Si, og den har været
med en del år. Se

<http://mathworld.wolfram.com/SieveofEratosthenes.html>

Venligst

Simon

--
The good Christian should beware of mathematicians, and all those who
make empty prophecies. The danger already exists that the
mathematicians have made a covenant with the devil to darken the
spirit and to confine man in the bonds of Hell. -- St. Augustin

---

> ... Metoden her er Eratosthenes Si, og den har været
> med en del år...

Den løsning må godt nok siges at være effektiv.
Jeg fik computeren til at finde alle primtal op til 200.000 i løbet af ca. 4
sekunder.
Problemet er bare, at jeg får hukommelsesproblemer hvis jeg sætter n over
200.000 (arbejder med lister i rekursiv programmeringssprog).

---

"Søren Hansen" <jes-s@mail1.stofanet.dk> wrote in message
news:3d074c07$0$14568$ba624c82@nntp01.dk.telia.net...

> Hvad er den mest effektive algoritme til at generere en liste af samtlige
> primtal gående fra 2 til x?

Når man vil have *alle* primtal mellem 2 og x, er Eratosthenes' si som
allerede nævnt den hurtigste - i hvert fald op til ret store 'x', og hvis
man kan leve med lineært pladsforbrug. Hvis 'x' bliver rigtig stor, må man
finde på andre metoder.

Hvis man ønsker at finde det mindste primtal større end et givet tal, y, kan
man bruge Rabin-testen. Den tester om et tal, n, er et primtal:
Der findes en "online-udgave" af testen her:
http://www.cryptomathic.com/labs/rabinprimalitytest.html

Den er baseret på at hvis n er et primtal, så er a^n = a (mod n), for alle
a. Hvis ligningen passer for 10-15 forskellige a'er, så er n med meget stor
sandsynlighed et primtal. Sandsynligheden for at n alligevel ikke er et
primtal kan fx gøres mindre end 10^(-25), hvilket er langt, langt mindre end
sandsynligheden for at computeren har regnet forkert grundet en
alfa-partikel fra det ydre rum, ramfejl, e.l.
Hvis 'n' ikke er et primtal, vil de fleste valg af 'a' afsløre dette.

Denne metode (Rabin-testen) er så hurtig at man kan bruge den til at finde
primtal på mange tusinde cifre. Det ville tage upraktisk lang tid med de
mere "naive" metoder.
Til RSA-kryptering skal man bruge primtal på omkring 200 cifre.


Mvh. Bjarke Ebert,
Cryptomathic A/S :)

---

"Bjarke Dahl Ebert" <bebert@worldonline.dk> writes:

> Når man vil have *alle* primtal mellem 2 og x, er Eratosthenes' si som
> allerede nævnt den hurtigste - i hvert fald op til ret store 'x',

I praksis, ja. Det er nemt at implementere Eratosthenes' si så den får
en køretid der er O(n*log(log n)). Jeg har set algoritmer der kørte
O(n), og set referencer til O(n/log(log n)).

Da der er O(n/log n) primtal mindre end n, vil en sådan algoritme
nødvendigvis være Omega(n/log n), så der er (omend begrænset) plads til
forbedringer.

..Henrik

--
"Det er fundamentalt noget humanistisk vås, at der er noget,
der hedder blød matematik."
--- citat Henrik Jeppesen, dekan for det naturvidenskabelige fakultet

---

Eratosthenes' si som de fleste svarere er inde på, er i øvrigt opkaldt
efter den græske matematiker (og forsker inden for talrige områder)
Eratosthenes fra Kyrene.

Man finder en biografi af Eratosthenes fra Kyrene her:

http://www-history.mcs.st-andrews.ac.uk/history/Mathematicians/Eratosthenes.html


--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)