Eratosthenes' si: Forskelle mellem versioner

'''Eratosthenes’ si''' er en [[Talfølge|talrække]], der fås ved at markere nogle [[tal]]. At ryste sien betyder at man mærker det mindste af de hidtil umærkede tal, og lader alle egentlige [[Mangefold|multipla]] af dette tal drysse ud af sien. Rækken fåsstartes således,ved at man fylder sien op med tallene større end 1; alle umærkede, dvs.

: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, ...

: <span style="text-decoration:underline;">2</span>, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, ...

Der rystes igen. HvervedHerved mærkes det mindste af de umærkede, altså tallet 3. Alle de andre tal, der er delelige med 3 drysser ud af sien. Tilbage bliver følgende tal i rækken:

: <span style="text-decoration:underline;">2</span>, <span style="text-decoration:underline;">3</span>, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, ...

Rystes der igen, bliverforbliver følgende tal i rækken:

: <span style="text-decoration:underline;">2</span>, <span style="text-decoration:underline;">3</span>, <span style="text-decoration:underline;">5</span>, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, ...

Hvis der rystes [[uendelig]]t mange gange resterer netop [[primtal]]lene i sien.

''';Som algoritme for computerkode'''.

For matematisk computerprogrammering vedtil beregning af primtal er Eratosthenes' si den hurtigste [[algoritme]] at bruge som basis for programmets kode, uansedtuanset programsprog. Det skyldes at algoritmen ikke trænger til nogen form afanvender division. I computerens CPU tagerkoster [[addition]], [[subtraktion]] og [[multiplikation]] af heltallerheltal kun to cykler at udføre, mens division trænger tilkræver mindst 17 cykler, ofte endnu flere. Der findes derudover mange måder at optimere koden på, især hvis man søger efter verdensrekorden affor største primtal. (Men al form affor division må begrænses, indklinkl. [[modulus]]).