Eratostenesen bahea

Eratostenes-en bahea 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.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

Adibideari dagokionez, $3^{2}<20$ 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 $p_{k}^{2}$ zenbakitik hastea da, $p_{k}$ izanik k-garren zenbaki lehena. Modu horretan, ez dira bi aldiz markatuko $p_{k}^{2}$ra arteko multiploak: $2p_{k},3p_{k},5p_{k},...,p_{k}^{2}$. Adibidean 3aren multiploak markatzea $3^{2}$ balioan hasiko genuke; 6 zenbakia bi aldiz markatua izatea ekidingo genuke. Algoritmoa amaituko da $p_{k}^{2}>n$ 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: $n$ zenbaki arrunt bat.

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

1. 2-tik $n$-rako zenbaki guztiak idatzi
2. $i$ indizea 2-tik $\lfloor {\sqrt {n}}\rfloor$-ra arte egin hurrengoa:
   • Baldin $i$ ez bada markatua izan orduan:
     • $j$ indizea $i$-tik $n\div i$ra arte, egin hurrengoa:
       • $i\times j$ posizioko zenbakia markatu
3. Emaitza: markatu gabeko zenbakiak

Notazioa:

• $\lfloor x\rfloor$ zoru-funtzioa da, hau da, $x$ baino txikiagoak diren zenbaki oso guztietan handiena ematen duen funtzioa.
• $a\div b$ zatiketa da, $a$ zenbakia $b$ zenbakiaz zatitzea.

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

Erreferentziak

• 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.

• Datuak: Q177898
• Multimedia: Sieve of Eratosthenes / Q177898