Kako odrediti sve proste brojeve koji nisu veći od n?
Prvo napišeš sve brojeve od 2 do n. Onda zaokružiš broj 2 i precrtaš sve ostale brojeve koji su deljivi njime.
Prvi neprecrtani i nezaokruženi broj je 3. Zaokružiš njega i precrtaš sve ostale brojeve koji su deljivi njime.
Prvi neprecrtani i nezaokruženi broj je 5. Zaokružiš njega i precrtaš sve ostale brojeve koji su deljivi njime.
Postupak nastavljaš sve dok ima neprecrtanih i nezaokruženih brojeva. Kada ih više ne bude bilo, zaokruženi su prosti, a precrtani složeni. Ovaj postupak se zove Eratostenovo sito.
Ako te zanima za neki konkretan broj da li je prost ili složen, a veći je od 1, onda treba da proveriš da li je deljiv sa nekim prostim brojem koji nije veći od njegovog kvadratnog korena. Dakle, prvo mu odrediš kvadratni koren zanemarujući decimale. Onda prethodnim postupkom odrediš sve proste brojeve koji nisu veći od korena tog broja, pa onda proveri deljivost tog broja sa tim prostim brojevima. Ako je deljiv sa nekim, onda je složen, a inače prost.
Primer: Proverimo da li je broj 101 prost.
Koren iz 101 je između 10 i 11. Odredimo sve proste brojeve koji nisu veći od 10. Najpre napišimo sve brojeve od 2 do 10.
2,3,4,5,6,7,8,9,10
Prvi us pisku je prost. To je broj 2. Izbacimo sve deljivo sa njime.Ostaju brojevi
3,5,7,9
Prvi od ovih brojeva je prost. To je 3. Izbacimo sve deljivo njime.
5,7
Prvi od ovih brojeva je prost. To je 5. Izbacimo sve deljivo njime.
7
Prvi od ovih brojeva je 7 i on je prost. Izbacimo sve deljivo njime i ne ostaje nam ništa.
Dakle, prosti brojevi koji nisu veći od 10 su 2,3,5 i 7. Proverimo deljivost broja 101 sa svakim od njih. Ispostavlja se da nije deljiv ni sa jednim, pa je prost.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.