Eratostenesen bahe

Eratostenesen baheaEuskalterm: [Hiztegi terminologikoa] [2002] zenbaki lehenak aurkitzeko algoritmo bat da, emandako n zenbaki arrunt bat baino txikiagoak direnen artean. Lehendabizi, taula bat egiten da 2 eta n arteko zenbaki arruntekin, jarraian multiploak markatzen dira hurrengo ordena jarraituz: 2tik hasita, haren multiplo guztiak markatzen dira, ostean, 3 zenbakiarekin prozedura bera burutzen da eta prozedura errepikatzen da markatuta ez dagoen zenbaki oso guztiekin ere. Markatu gabe geratzen diren zenbakiak lehenak dira. Prozedura hori behin eta berriz errepikatzen da, aurkitutako azken zenbaki lehenaren hurrengo zenbakiaren karratua n baino handiagoa den arte.

 Bahetze-prozesua 
Honako adibidearen bidez, 20 baino txikiagoak diren zenbaki lehenak aurkitzeko eman beharreko urratsak azaltzen dira. Algoritmoan zehar zenbakiak bereiztuko dira: lehenak, markatutakoak, markatu gabekoak.

1. Lehenengo urratsa: 2 eta aukeratutako zenbaki arruntaren arteko zenbakiak zerrendatu. Hasteko, zenbaki guztiak markatu gabekoak dira.

 {| cellspacing="0" cellpadding="2" border="1"
| bgcolor="#d1c4ad" |2
| bgcolor="#d1c4ad" |3
| bgcolor="#d1c4ad" |4
| bgcolor="#d1c4ad" |5
| bgcolor="#d1c4ad" |6
| bgcolor="#d1c4ad" |7
| bgcolor="#d1c4ad" |8
| bgcolor="#d1c4ad" |9
| bgcolor="#d1c4ad" |10
| bgcolor="#d1c4ad" |11
| bgcolor="#d1c4ad" |12
| bgcolor="#d1c4ad" |13
| bgcolor="#d1c4ad" |14
| bgcolor="#d1c4ad" |15
| bgcolor="#d1c4ad" |16
| bgcolor="#d1c4ad" |17
| bgcolor="#d1c4ad" |18
| bgcolor="#d1c4ad" |19
| bgcolor="#d1c4ad" |20
|}

2. Bigarren urratsa: Markatu gabe dagoen lehenengo zenbakia lehentzat hartzen da.

 {| cellspacing="0" cellpadding="2" border="1"
| bgcolor="#ff0000" |2
| bgcolor="#d1c4ad" |3
| bgcolor="#d1c4ad" |4
| bgcolor="#d1c4ad" |5
| bgcolor="#d1c4ad" |6
| bgcolor="#d1c4ad" |7
| bgcolor="#d1c4ad" |8
| bgcolor="#d1c4ad" |9
| bgcolor="#d1c4ad" |10
| bgcolor="#d1c4ad" |11
| bgcolor="#d1c4ad" |12
| bgcolor="#d1c4ad" |13
| bgcolor="#d1c4ad" |14
| bgcolor="#d1c4ad" |15
| bgcolor="#d1c4ad" |16
| bgcolor="#d1c4ad" |17
| bgcolor="#d1c4ad" |18
| bgcolor="#d1c4ad" |19
| bgcolor="#d1c4ad" |20
|}

3. Hirugarren urratsa: Aurreko urratsean aipatutako zenbakiaren multiploak markatzen dira. Markatuak izan diren zenbakiak ez dira zenbaki lehen.

 {| cellspacing="0" cellpadding="2" border="1"
| bgcolor="#ff0000" |2
| bgcolor="#d1c4ad" |3
| 4 
| bgcolor="#d1c4ad" |5
| 6 
| bgcolor="#d1c4ad" |7
| 8 
| bgcolor="#d1c4ad" |9
| 10 
| bgcolor="#d1c4ad" |11
| 12 
| bgcolor="#d1c4ad" |13
| 14 
| bgcolor="#d1c4ad" |15
| 16 
| bgcolor="#d1c4ad" |17
| 18 
| bgcolor="#d1c4ad" |19
| 20 
|}

4. Laugarren urratsa: Markatu gabeko zenbaki txikienaren karratua 20 baino txikiagoa den bitartean, bigarren urratsera bueltatu. Bestela, algoritmoa amaitzen da. Markatu gabeko zenbaki guztiak zenbaki lehenak dira.

 {| cellspacing="0" cellpadding="2" border="1"
| bgcolor="#ff0000" |2
| bgcolor="#0000ff" |3
| 4 
| bgcolor="#d1c4ad" |5
| 6 
| bgcolor="#d1c4ad" |7
| 8 
| 9 
| 10 
| bgcolor="#d1c4ad" |11
| 12 
| bgcolor="#d1c4ad" |13
| 14 
| 15 
| 16 
| bgcolor="#d1c4ad" |17
| 18 
| bgcolor="#d1c4ad" |19
| 20 
|}

Adibideari dagokionez,  denez, bigarren urratsera bueltatu behar da. Hurrengo iterazioan 5 zenbakia izango da markatu gabeko zenbakirik txikiena, eta 5aren karratua 20 baino handiagoa denez, algoritmoa amaitu eta markatu gabeko zenbaki guztiak lehenak direla esaten da.

Hortaz, aukeratutako tarte horretan algoritmoa aplikatu ostean, 2 eta 20 arteko zenbaki lehenak lortzen dira: 2,3,5,7,11,13,17,19.

 Finketa 
Bahetze-prozesuaren finketa egiteko hainbat modu daude. Izan ere, hainbat zenbaki bi aldiz markatzen dira, urrats bat baino gehiagotan zenbaki bera markatzea erabakitzen delako. Aurreko adibidean, 2aren multiploak markatu direnean 4, 6, 8, 10, 12, 14, 16, 18 eta 20 zenbakiak markatu dira. Algoritmoaren hurrengo iterazioan 3aren multiploak markatu dira, hau da, 6, 9, 12, 15 eta 18. Ikusten den bezala, 6 eta 12 zenbakiak bi aldiz markatuak izan dira. Behin baino gehiagotan markatuak izango diren zenbakiak murrizteko modu bat, markatze-prozesua aldiero  zenbakitik hastea da,  izanik k-garren zenbaki lehena. Modu horretan, ez dira bi aldiz markatuko ra arteko multiploak: . Adibidean 3aren multiploak markatzea  balioan hasiko genuke; 6 zenbakia bi aldiz markatua izatea ekidingo genuke. Algoritmoa amaituko da  denean, hortik aurrera ez dagoelako markatua izan daitekeen zenbakirik.

Finketa egiteko beste modu bat, algoritmoaren lehen urratsean zenbaki bikoiti guztiak markatzea da, 2 baino handiagoak diren zenbaki bikoitiak ez baitira inoiz zenbaki lehen izango (2 zenbakiak zatitzen dituelako). Behin hori eginda, algoritmoarekin jarraituko litzateke.

 Sasikodea 
Sarrera:  zenbaki arrunt bat.

Irteera: Sarrerako zenbakia baino txikiagoak edo berdinak diren zenbaki lehenen multzoa.

 2-tik -rako zenbaki guztiak idatzi
  indizea 2-tik -ra arte egin hurrengoa:
 Baldin  ez bada markatua izan orduan:
  indizea -tik ra arte, egin hurrengoa:
  posizioko zenbakia markatu
 Emaitza: markatu gabeko zenbakiak

Notazioa:
  zoru-funtzioa da, hau da,  baino txikiagoak diren zenbaki oso guztietan handiena ematen duen funtzioa.
  zatiketa da,  zenbakia  zenbakiaz zatitzea.

Algoritmoaren inplementaziorako, normalean  elementuz osatutako bektore bat erabiltzen dira, datu-mota logikoa izanik. Horrela,  posizioan Egiazkoa agertzen bada  markatua izan dela esan nahiko du eta Faltsua izango da kontrako kasuan.

 Erreferentziak 

 Bibliografia 
 Samuel Horsley (1772). «. or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S.». Philosophical Transactions (1683-1775) 62.
 Walter Mora F. «Criba de Eratóstenes». Revista digital Matemática: Educación e Internet 7 (2)
 Zientzia eta teknologiaren hiztegi entziklopedikoa (ZTH) «Eratostenesen bahe»

 Ikus, gainera 
 Zenbaki lehenen test

 Kanpo estekak 

 Eratostenesen bahearen inplementazioa programazio lengoaia ezberdinetan.

Kategoria:Zenbaki lehenak
Kategoria:Algoritmoak