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.
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
- Algoritmy.net: Eratosthenovo síto
- Pavel Töpfer: Eratosthenovo síto, přednášky + programy