Pascal – Prvočísla – Eratosthenovo síto

Datum vydání: 2011-04-23 11:37:26 ; aktualizováno: 2019-11-10 08:51:24

Program vytiskne prvočísla do zadané hodnoty N. Použije se při tom algoritmu tzv. Eratosthenova síta.

Zdrojový kód Free Pascal

program Prvocisla;
uses Crt;
const MAX_N = 10000;
var
    n, i, nasobek: integer;
    sito: array[2..MAX_N] of boolean; // true = je prvocislo, false = neni prvocislo
begin
    clrScr;

    writeln('Program vypise prvocisla do zadane hodnoty N <= ', MAX_N);
    write('Zadejte kladne cele cislo N: ');
    readln(n);

    if (n > 0) and (n <= MAX_N) then
    begin
        for i := 2 to n do
            sito[i] := true; // nastavime vsechna cisla na prvocisla
        for i := 2 to n do
        begin
            if sito[i] then // pokud je prvocislo
            begin
                nasobek := 2 * i;
                while nasobek <= n do
                begin
                    sito[nasobek] := false; // nasobky nejsou prvocisla
                    nasobek := nasobek + i;
                end;
            end
        end;

        // vytiskneme prvocisla
        write('Prvocisla jsou: ');
        for i := 2 to n do
        begin
            if (sito[i]) then
                write(i, ' ');
        end;
    end;

    repeat
    until keyPressed;
end.

Optimalizace

Místo průchodu do n v kódu

        for i := 2 to n do

lze použít zkrácený průchod do n/2 či dokonce do √n.

Zdrojový soubor

soubor prvocisla.pas

Spuštění programu

Program vypise prvocisla do zadane hodnoty N <= 10000
Zadejte kladne cele cislo N: 100
Prvocisla jsou: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83
89 97

Popis algoritmu

Síto se tomu říká proto, protože nejprve si všechna čísla označíme jako prvočísla a postupně je "prosíváme" tak, že nakonec nám, obrazně řečeno, čísla složená (neprvočísla) zůstanou pod sítem a prvočísla nad sítem.

Datově si prvočísla můžeme uložit například takto do pole Sito.

Pole si uděláme tak velké, jak potřebujeme. Zde budeme uvažovat pole od 2 do 10 000 pro prvočísla do 10 000. Počítám s indexací pole od 2. Nula a jednička prvočísly nejsou. Index pole nám označuje požadované číslo a logická hodnota nám označuje, zda jde o prvočíslo. Hodnota true tedy značí, že jde o prvočíslo, hodnota false, že nejde o prvočíslo.

Nejprve si všechna čísla v požadovaném rozsahu označíme jako prvočísla. Konkrétně zde si naplníme pole Sito hodotami true.

Postupně bereme čísla od nejnižších pozic, o nichž víme, že jsou prvočísla. Bereme nejnižší číslo, o kterém stoprocentně víme, že je prvočíslo. Pak si označíme všechny zbývající násobky tohoto čísla jako neprvočísla. Následně přistoupíme k dalšímu nejnižšímu prvočíslu a opět označíme všechny další jeho násobky za neprvočísla. Takto projdeme celým polem a nakonec nám zbydou pouze prvočísla.

Příklad

Konkrétně začínáme tedy od čísla 2. O číslech 0 a 1 víme, že nejsou prvočísla, takže je v poli vůbec nebudeme mít. Víme, že každé nejbližší další číslo, počínaje 2, které jsme nevyhodili, je 100% prvočíslo. Vezmeme tedy toto nejnižší prvočíslo a z pole Sito vyřadíme jako prvočísla všechny jeho násobky.

Například pole od 0 do 17 po projeti sitem prvocisla 2 bude vypadat takto:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Pak jdeme na další nejnižší prvočíslo, které je větší než 2. Je jím číslo 3. A opět z pole vyhodíme (nastavíme na false) všechny jeho násobky.

Pole od 2 do 17 po projeti sitem prvocisla 2, 3 bude vypadat už více „proseté“:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Pak máme číslo 4, ale to už je označeno jako číslo složené (není prvočíslo), tak musíme najít další nejbližší vyšší prvočíslo. Je jím 5 a opět si označíme všechny násobky čísla 5 jako neprvočísla. Tímto způsobem nám prvočísela řídnou a nakonec zbydou pouze prvočísla.

Další informace

Vyhledávání

Články na ITčku: