Eratostenovo sito: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
Nema sažetka uređivanja |
|||
Redak 1:
[[Datoteka:Sieve_of_Eratosthenes_animation.gif|mini|400 px| Animirano Eratostenovo sito]]
Na slici je demonstracija traženja prostih brojeva manjih od 121. Napisani su svi prirodni brojevi od 2 do 120. U prvom koraku je najmanji neoznačeni broj 2, zato ga označimo crvenom bojom, a onda nježnijom nijansom crvene boje "precrtamo" ostale njegove višekratnike. Nakon toga je najmanji neoznačeni broj broj 3. Njega "zaokružimo" zelenom, a nježnijom nijansom zelene "precrtamo" višekratnike broja 3. Nakon toga je najmanji neoznačeni broj 5. Njega označimo plavom bojom, a njegove višekratnikom svjetlijom nijansom plave. Isto napravimo s brojem 7. Nakon toga je na redu broj 11. No sve njegove višektratnike smo ionako već precrtali. Zato radi jednostavnosti sve ostale proste brojeve označimo istom bojom, iako to baš nije sasvim korektno.]]▼
'''Eratostenovo sito''' (rešeto) je jednostavan [[algoritam]] za dobivanje svih [[prosti broj|prostih brojeva]] manjih od unaprijed izabranoga prirodnog broja. Osmislio ga je grčki matematičar, geograf i astronom [[Eratosten]].
Postupak dobivanja prostih brojeva pomoću Eratostenovog sita:
Line 11 ⟶ 9:
Postupak završi u konačno mnogo koraka, jer na početku imamo konačno mnogo brojeva, a u svakom koraku barem jedan broj označimo. Zaokruženi brojevi su [[prosti broj|prosti brojevi]]. Precrtani brojevi su [[složeni broj|složeni brojevi]].
▲Na slici je demonstracija traženja prostih brojeva manjih od 121. Napisani su svi prirodni brojevi od 2 do 120. U prvom koraku je najmanji neoznačeni broj 2, zato ga označimo crvenom bojom, a onda nježnijom nijansom crvene boje "precrtamo" ostale njegove višekratnike. Nakon toga je najmanji neoznačeni broj broj 3. Njega "zaokružimo" zelenom, a nježnijom nijansom zelene "precrtamo" višekratnike broja 3. Nakon toga je najmanji neoznačeni broj 5. Njega označimo plavom bojom, a njegove višekratnikom svjetlijom nijansom plave. Isto napravimo s brojem 7. Nakon toga je na redu broj 11. No sve njegove višektratnike smo ionako već precrtali. Zato radi jednostavnosti sve ostale proste brojeve označimo istom bojom, iako to baš nije sasvim korektno.
Iako jako jednostavan, opisani postupak nije baš učinkovit za traženje velikih prostih brojeva. Tek za ilustraciju algoritma je priložen programski kod u programskom jeziku VB.NET:
| |||