P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 1 (1973/1974) Številka 2 Strani 109-111
Franci Oblak:
ERATOSTENOVO REŠETO
Ključne besede: matematika.
Elektronska verzija: http://www.presek.si/1/1-2-Oblak.pdf
© 1973 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
ERATOSTENOVO REŠETO Franci Oblak
Imejmo množico naravnih števil tf = (1,2,3f...*•,}* Število a^N je večkratnik števila , če moremo zapisati a kot; a = £», kjer je nz N. Število b imenujemo deli tel j števila am Primer: 6 ^ 2.3| 6 je večkratnik (dvakratnik) števila 3 in 3 je
delitelj števila 6. Po vrsti so večkratniki števila 3: 3, 6, *•• •
Praštevila so naravna števila, ki imajo točno dva delitelja: 1 in število samo., Števila, ki imajo več deliteljev, so sestavljena števila. Število 1 ni niti praštevilo niti sestavljeno število, ker ima en sam delitelj, namreč 1.
	(2)	(3)	X	(5)	X	C)	X		X
(¡0,	X	(|3)	X	X	X	(17)		(19)	X
X	X		X	X	X		X		
(31)				X			X		><
(fi)					X	(p)	X	X	X
Kako poiščemo iz množice prvih n naravnih števil vsa praštevila do n ? Eratostenes Kyrenčan (27 6— 194? pr.n.fii) (glej 1 ) je predlagal naslednje: napišemo tabelo naravnih števil od 1 do n. Mi bomo vzeli primer, da je n = 50. Prečrtamo Število 1, ker ni praštevilo. Prvo neprečrtano število, ki sledi, je 2; to je praštevilo.
a)	Prečrtamo po vrsti vse večkratnike praštevila Z do n.
b)	Prvo neprečrtano število, ki sledi 2, je 3; to je prašte-vilo.
a} Prečrtamo po vrsti vse večkratnike praštevila 3 do m.
b} Prvo neprečrtano število, ki sledi številu 3, je 5; to je praštevilo.
Tako nadaljujemo:
a) Prečrtamo po vrsti vse večkratnike praštevila p do n.
b} Prvo neprečrtano Število, ki sledi številu p, je zopet praštevilo.
Ponavljamo postopek pod a) in b) do /n, ker mora imeti vsako sestavljeno število med svojimi delitelji vsaj en delitelj -praštevilo, ki ni večje od Vn, Glej 2 .
Pri nas je /n = /hO = 7. vsa števila, ki so ostala neprečr-tana do n, so praštevila.
Torej so praštevila od 1 do 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Poglejmo Se od kod naziv Eratostenovo reSeto. V literaturi najdemo izjavi:
1. V času Eratostenesa so pisali na voSSene tablice. Namesto črtanja (sestavljenih) Števil so tablico na tem mestu preluknjalii tablica se je spremenila v reSeto, (I.Ja.Depman: Zgodovina aritmetike, Moskva, 1965).
1	Glej: France Križanič: Križem po matematiki (str. 41), Ljub-
ljanaj 1960
2	Dokaz te lastnosti in druge zanimivosti o praštevilih bo sijajno opisane V knjigi Ivana Vidava: Rešeni in nereSeni problemi matematike, Ljubljana, MK, 197Z.
110
2. Da bi dobil tabelo praštevil, je Eratostenes * ki je pisal na napet papirus* namesto* da bi črtal * kar preluknjal sestavljena števila. Od tod ime "Eratostenovo ieleto", praštevila ostanejo na rešetu. (G*J*Glej ser: Zgodovina matematike v šoli, Moskva* 1364}.
Preizkusite, Če ste opisani postopek razumeli ter določite vsa praštevila od 1 do 170. Izpišite jih po vrsti.
Frana Oblak