10. astea | Eratostenes-en bahea (I)

Galbahe (edo bahe) baten irudia. Galbaheri esker aleak sailka daitezkeen bezala, zenbaki zerrenda bati galbahe logikoren bat aplikatuz zenbakien segida desberdinak lor daitezke, adibidez: zenbaki lehenak identifikatzeko Eratostenes matematikari greziarrak asmatutakoa

Ariketa honi bi modutan ekingo diogu:

• 10. astea | Eratostenes-en bahea (I) zenbaki osoen bi dimentsiotako array bat erabiliz
• 11. astea | Eratostenes-en bahea (II) erregistroen dimentsio bakarreko array bat erabiliz

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, hurrengo zenbakiarekin jarraituko da baina bi egoera daude:
• Hurrengo zenbakia markaturik gabe dago, adibidez 3 zenbakia, eta lehen bezala bere multiplo guztiak markatzen dira
• Hurrengo zenbakia markaturik dago, adibidez 4 zenbakia, kasu honetan ez da ezer markatzen eta bere hurrengo zenbakia hartzen da
• 5ekin markatu beharko litzateke (goiko lehen kasua), 6kin ez litzateke ezer markatuko (goiko bigarren kasua), 7ekin markatu beharko litzateke (goiko lehen kasua), 8, 9 eta 10ekin ez litzateke ezer markatuko (goiko bigarren kasuak), e.a.
  Prozedura errepikatzen da hau betetzen den bitartean: (MarkatuGabekoZenbakia)² < n. Beste modu batez esanik, markatu gabeko zenbakiaren karratua n baino handiagoa denean eten prozesu errepikakorra

Eratostenes-en bahearen animazioa 120 baino gutxiagoko zenbaki lehenentzat:

SKopp at German Wikipedia, CC BY-SA 3.0, via Wikimedia Commons

Hona hemen datu-taularen irudia MAX konstanteak 21 balio duenean, non 0 markak zenbaki lehen adierazten duen eta 1 markak zenbaki zatigarri adierazten duen:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	zenbakia
2	0	0	1	0	1	0	1	1	1	0	1	0	1	1	1	0	1	0	1	1	marka
	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21

Ariketaren balizko kodea ikusi:

(*
   Muga den kopuru arrunta emanez, muga hori baino txikiagoak diren
   "Zenbaki Lehenak" lortzeko metodo bat aurkitu zuen Eratostenesek.
   
   Algoritmoa:
   ----------
   2tik iMuga-rako zenbakiak zerrenda batean jartzen dira. Lehenengo, 2ren
   multiplo guztiak markatzen dira, eta 2 zenbakia emaitza den lehenen
   zerrendari gehituko zaio. Ondoren, 3ren multiplo guztiak markatuko dira,
   eta 3 zenbakia gehituko zaio lehenen zerrendari. Gero, 4ari begiratzen
   zaio, markatuta dagoela ikusten da, eta horrek esan nahi du 2rekin 
   zatigarria dela, eta, beraz, ez da lehena. Ondoren, 5era iristen da;
   markatuta ez dagoenez, lehena da, bere multiplo guztiak markatzen dira
   eta lehenen zerrendara gehituko da.
   Prozesu errepikakorra bukatzeko baldintza: Une jakin batean aztertuko den
   zenbakiaren karratua iMuga-tik beherakoa bada, jarraitu beharra dago.
   Bestela, algoritmoa amaitu egiten da, eta markatu gabe geratu diren
   guztiak zenbaki lehenak dira (emaitza-zerrendari gehitu beharrekoak).
   
   Animazio hau ikusi:
   https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif

   Bi programa hauek aztertu:
      * EratostenesenBahea_1 zenbaki osoen bi dimentsiotako array bat
      * EratostenesenBahea_2 erregistroen dimentsio bakarreko array bat
*)

Program EratostenesenBahea_1;
const
   MAX = 120;
type
   taiDatuak = array[1..2, 2..MAX] of integer;   // 2 errenkada eta MAX-1 zutabe
   taiLehenak = array[1..MAX-1] of integer;


procedure DatuakLortu(var aiDatuak: taiDatuak; var iLuzeraDatuak: integer);
var
   k: integer;
begin
   iLuzeraDatuak := MAX;
   for k:=2 to iLuzeraDatuak do
   begin
      aiDatuak[1,k] := k;
      aiDatuak[2,k] := 0;   // 0 (FALSE) lehena eta 1 (TRUE) zatigarria
   end;
end;


procedure DatuakIkusi(const aiDatuak: taiDatuak; iLuzeraDatuak: integer);
var
   k: integer;
   iKont_0: integer;    // lehenen kopurua
   iKont_1: integer;    // zatigarrien kopurua
begin
   iKont_0 := 1;    // 1 zenbakia lehena da eta ez dugu begizta barruan prozesatuko
   iKont_1 := 0;    // zatigarrien kopurua
   writeln('--------------------------------------------------------------------------------');
   write('   1-LEHEN');
   for k:=2 to iLuzeraDatuak do
   begin
      write(aiDatuak[1,k]:4);
      if aiDatuak[2,k]=0 then
      begin
         write('-LEHEN');
         iKont_0 := iKont_0 +1;
      end
      else
      begin
         write('__ZAT.');
         iKont_1 := iKont_1 +1;
      end;
   end;
   writeln;
   writeln('--------------------------------------------------------------------------------');
   writeln(' Zenbakien kopurua = ', iLuzeraDatuak, '     Lehenen kopurua = ', iKont_0, '     Zatigarrien kopurua = ', iKont_1);
end;


procedure LehenakLortu(const aiDatuak: taiDatuak; iLuzeraDatuak: integer;
                       var aiLehenak: taiLehenak; var iLuzeraLehenak: integer);
var
   k: integer;
begin
   iLuzeraLehenak := 1;
   aiLehenak[iLuzeraLehenak] := 1;
   for k:=2 to iLuzeraDatuak do
   begin
      if aiDatuak[2,k]=0 then
      begin
         iLuzeraLehenak := iLuzeraLehenak +1;
         aiLehenak[iLuzeraLehenak] := aiDatuak[1,k];
      end;
   end;
end;


procedure LehenakIkusi(const aiLehenak: taiLehenak; iLuzeraLehenak: integer);
var
   k: integer;
begin
   writeln('********************************************************************************');
   for k:=1 to iLuzeraLehenak do
   begin
      write(aiLehenak[k]:3, ', ');
   end;
   writeln;
   writeln('********************************************************************************');
   writeln('  iLuzeraLehenak = ', iLuzeraLehenak);
end;


{-----------------------programa nagusia eta bere aldagaiak-----------------------}
var
   aiDatuak: taiDatuak;
   iLuzeraDatuak: integer;
   aiLehenak: taiLehenak;
   iLuzeraLehenak: integer;
   iIterazioa: integer;
   k: integer;
begin
   DatuakLortu(aiDatuak, iLuzeraDatuak);
   writeln;
   writeln('Hasierako datuak:');
   DatuakIkusi(aiDatuak, iLuzeraDatuak);
   writeln;
   writeln;
   writeln('1 zenbakia alde batera utzirik, prozesu errepikakorra 2 zenbakiarekin hasiko da');
   writeln;
   writeln;

   iIterazioa := 2;         // lehenengo iterazioan, 2ren multiploak markatzen dira
   repeat
      writeln('================================================================================');
      if aiDatuak[2,iIterazioa] = 0 then
      begin
         write(iIterazioa, ' zenbakia lehena da, ');
         writeln(iIterazioa, ' zenbakiaren multiploak markatzen...');
         for k:=iIterazioa+1 to MAX do
         begin
            if aiDatuak[1,k] mod iIterazioa = 0 then
            begin
               aiDatuak[2,k] := 1;    // zatigarria delako 1 marka dagokio
               writeln(aiDatuak[1,k]:4, ' zenbakia markaturik zatigarria delako');
            end;
         end;
      end
      else
         writeln(iIterazioa, ' zenbakia zatigarria da');

      writeln(iIterazioa, ' arteko datuak:');
      DatuakIkusi(aiDatuak, iLuzeraDatuak);
      writeln('================================================================================');
      iIterazioa := iIterazioa +1;
      if iIterazioa*iIterazioa <= MAX then
         writeln(' ', iIterazioa, 'x', iIterazioa, ' = ', iIterazioa*iIterazioa, ' <= ', MAX, '   prozesu errepikakorrarekin jarraitu')
      else
         writeln(' ', iIterazioa, 'x', iIterazioa, ' = ', iIterazioa*iIterazioa, ' > ', MAX, '   prozesu errepikakorra amaitu');
      writeln;
      writeln;
   until iIterazioa*iIterazioa > MAX;

   LehenakLortu(aiDatuak, iLuzeraDatuak, aiLehenak, iLuzeraLehenak);
   writeln('Lehenen zerrenda:');
   LehenakIkusi(aiLehenak, iLuzeraLehenak);
   
   writeln;
   writeln;
   write('ENTER sakatu exekuzioa amaitzeko... ');
   readln;
end.

 

Eratostenes (antzinako grezieraz: Ἐρατοσθένης; K.a. 276 inguru - K.a. 195 inguru) matematikari, geografo, kirolari, poeta eta astronomo greziarra izan zen. Alexandriako Liburutegia famatuaren zuzendari izendatu zuten eta aurkikuntza ugari egin zituen, hala nola, latitude eta longitude sistema. Eratostenes ezaguna da Lurraren zirkunferentzia kalkulatzen lehen greziarra izan zelako, baita Lurraren ardatzak duen makurdura. Bestalde, garaiko ezagutza geografikoaren araberako mundu mapa eratu zuen ere.