Eratosthenes' si

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

Eratosthenes’ si er en talrække, der fås ved at markere nogle tal. At ryste sien betyder at man mærker det mindste af de umærkede tal, og lader alle egentlige multipla af dette tal drysse ud af sien. Rækken fås således, 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,...

Sien rystes én gang, hvor det mindste tal mærkes, altså tallet 2; alle de lige tal drysser ud af sien. Tilbage bliver følgende tal i rækken:

2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,...

Der rystes igen. Hverved 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:

2,3,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,...

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

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,...

Hvis der rystes uendelig mange gange resterer netop primtallene i sien.

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

Matematik Stub
Denne artikel om matematik er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.