Eratostena sietsnua Ge080(14mbi150empsiznsckipzönoliv
Ilustrācija Eratostena sieta algoritmam skaitļiem, kas nepārsniedz 120
Eratostena siets ir vienkāršs algoritms visu to pirmskaitļu atrašanai, kas nepārsniedz kādu dotu naturālu skaitli. Algoritmu izdomāja sengrieķu matemātiķis Eratostens.
Algoritma apraksts[labot šo sadaļu | labot pirmkodu]
Algoritms visu pirmskaitļu, kas nepārsniedz n, atrašanai ir šāds:
- uzrakstām rindā naturālos skaitļus no 2 līdz n: 2, 3, 4, ..., n.
- atstājam pirmo no tiem (2) un izsvītrojam visus nākamos skaitļus, kas dalās ar 2;
- atrodam mazāko neizsvītroto skaitli (3) un izsvītrojam visus nākamos skaitļus, kas dalās ar 3;
- procesu atkārtojam, līdz iegūts tāds neizsvītrotais skaitlis p, ka p2 > n.
Tad visi neizsvītrotie skaitļi ir pirmskaitļi.
Ārējās saites[labot šo sadaļu | labot pirmkodu]
- Eric W. Weisstein, Sieve of Eratosthenes, MathWorld.
- Pirmskaitļu algoritmi (1) - Eratostena siets[novecojusi saite].
 | Šis ar matemātiku saistītais raksts ir nepilnīgs. Jūs varat dot savu ieguldījumu Vikipēdijā, papildinot to. |