Eratosthenes såll
Wikipedia
Eratosthenes såll är en enkel algoritm som används för att hitta primtal.
Man kan utföra den för hand för till exempel de 100 första talen genom att först skriva upp dessa (utom 1). Sedan ringar man in 2 och stryker över alla jämna tal. I nästa steg ringar man in 3 och stryker över vart tredje tal. Sedan ringar man in nästa tal som ej är överstruket, dvs. 5, och stryker över alla tal delbara med 5. Sedan fortsätter man så till dess att alla tal till 100 är antingen överstrukna eller inringade. Alla inringade tal är primtal.
[redigera] Se även
- Matematik
- Gaussiskt primtal
- Mersenneprimtal
- Primtalssatsen
- Perfekt tal
- Relativt prima
- Primtalstvilling
- Aritmetikens fundamentalsats
