Eratosthenes såll
Eratosthenes såll är en algoritm som används för att hitta primtal. Den fungerar enligt följande:- Gör en lista över alla heltal mellan 1 och n.
- För varje heltal mellan 1 och roten ur n stryk alla multiplar av det lägsta icke strukna talet i listan.
Numren som blir kvar är primtalen mellan 1 och n.
Exempel
roten ur 20 är ungefär 4.5
Sollar | Lista-------+---------------------------------------------------- | 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 | X 3 X 5 X 7 X 9 XX 11 XX 13 XX 15 XX 17 XX 19 XX 3 | X 3 X 5 X 7 X X XX 11 XX 13 XX XX XX 17 XX 19 XX 4 | Behöver ej utföras då 4 är struken
Primtalen mellan 2 och 20 är således3, 5, 7, 11, 13, 17, 19
Artikeln skriven 2009-01-17 av Learning4sharing
Inga kategorier för denna artikel än...Intresserad av fler artiklar?
Patrick MooreValfångstfartyg
Kaskelot
Fältbiologen
Taiga Rescue Network
Klarälven
Loska
Spottkopp
Gehör