Eratosthenes' si: Forskelle mellem versioner
No edit summary |
Hanne123 (diskussion | bidrag) m sprogrettelser mm. |
||
Linje 1: | Linje 1: | ||
'''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 umærkede tal, og lader alle egentlige [[Mangefold|multipla]] af dette tal drysse ud af sien. Rækken |
'''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 startes 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,... |
: 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: |
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: |
||
: <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,... |
: <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. |
Der rystes igen. Herved 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,... |
: <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, |
Rystes der igen, forbliver 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,... |
: <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]] mange gange resterer netop [[primtal]]lene i sien. |
Hvis der rystes [[uendelig]]t mange gange resterer netop [[primtal]]lene i sien. |
||
;Som algoritme for computerkode |
|||
For matematisk computerprogrammering |
For matematisk computerprogrammering til beregning af primtal er Eratosthenes' si den hurtigste [[algoritme]] at bruge som basis for programmets kode, uanset programsprog. Det skyldes at algoritmen ikke anvender division. I computerens CPU koster [[addition]], [[subtraktion]] og [[multiplikation]] af heltal kun to cykler at udføre, mens division kræ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 for største primtal. (Men al form for division må begrænses, inkl. [[modulus]]). |
||
[[Kategori:Primtal]] |
[[Kategori:Primtal]] |
||
Versionen fra 13. aug. 2014, 20:50
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 hidtil umærkede tal, og lader alle egentlige multipla af dette tal drysse ud af sien. Rækken startes 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, ...
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. Herved 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, forbliver 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 uendeligt mange gange resterer netop primtallene i sien.
- Som algoritme for computerkode
For matematisk computerprogrammering til beregning af primtal er Eratosthenes' si den hurtigste algoritme at bruge som basis for programmets kode, uanset programsprog. Det skyldes at algoritmen ikke anvender division. I computerens CPU koster addition, subtraktion og multiplikation af heltal kun to cykler at udføre, mens division kræ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 for største primtal. (Men al form for division må begrænses, inkl. modulus).
Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den. |