Eratosthenovo síto: Porovnání verzí
Smazaný obsah Přidaný obsah
Wikipedie není učebnice programování ani návodem na tvorbu skriptů v jednolivých programovacích jazycích, tedy tu jejich příklady nemají co dělat, na zbytek upravit |
revert - prilkad v Pascalu muze byt pro nekoho srozumitelnejsi nez slovni popis |
||
Řádek 29:
Výsledný seznam prvočísel v rozsahu 2–20: '''2, 3, 5, 7, 11, 13, 17, 19'''.
== Zdrojový kód v jazyce Pascal ==
<source lang="pascal">
program ErSito;
const
MaxN = 20;
var
Pole: array [2 .. MaxN] of boolean;
i, j: integer;
begin
{inicializace: nejprve předpokládáme, že vše jsou prvočísla}
for i := 2 to MaxN do
Pole[i] := true;
i := 1;
repeat
i := i + 1;
{najdeme prvni cislo, u kterého je true}
while (i<MaxN) and (not Pole[i]) do i := i + 1;
{optimalizace: nemá smysl hledat násobky nižších čísel označené dříve}
j := i;
{najdeme všechny násobky daného prvočísla, které tudíž nejsou prvočísla}
while j*i<=MaxN do
begin
Pole[j*i] := false;
j := j + 1;
end;
until i>=sqrt(MaxN); {optimalizace: stačí hledat pouze po odmocninu z MaxN}
{výpis prvočísel}
for i := 2 to MaxN do
if Pole[i] then
Writeln(i);
end.
</source>
== Zdrojový kód v jazyce Java ==
<source lang="java">
int MaxN = 1024;
boolean[] Pole = new boolean[MaxN+1];
int i,j;
for (i=2;i<(MaxN+1);i++) { /* Inicializace pole (vse jsou prvocisla a postupne budem vyrazovat) */
Pole[i] = true;
}
i=2;
while (i*i <= MaxN) { /* dokud mocnina prvniho cisla na seznamu je mensi nez nejvetsi */
if (Pole[i]){ /* pokud je i stale na seznamu (nezkoumej nasobky 4, kdyz jsme uz vyhodili nasobky 2 */
j=2; /* j bude novy nasobek */
while (i*j <= MaxN) {
Pole[j*i] = false; /* cislo slozene */
j++;
}
}
i++;
}
</source>
== Zdrojový kód v jazyce C++ ==
<source lang="c">
#include <iostream>
#include <set>
using namespace std;
int main()
{
int max;
cout << "Zadejte cislo do ktereho chcete vypsat prvocisla" << endl;
cin >> max;
set<int> sito, prvocisla;
set<int>::iterator p;
int dalsi, nasobek;
for (int i = 2; i <= max; i++)
sito.insert(i);
dalsi = 2;
while (!sito.empty())
{
while (sito.count(dalsi) == 0) dalsi++;
prvocisla.insert(dalsi);
nasobek = dalsi;
while (nasobek <= max)
{
sito.erase(nasobek);
nasobek += dalsi;
}
}
for (p = prvocisla.begin(); p != prvocisla.end(); p++)
cout << *p << ' ';
cout << endl;
}
</source>
== Zdrojový kód v jazyce Python ==
<source lang="python">
MaxN = 1024 #horni hranice seznamu cisel
SeznamN = range(2,MaxN+1) #vytvoreni seznamu cisel v rozpeti <2,1024>
Prvocisla = [] #vytvoreni (prozatim) prazdneho seznam prvocisel
while SeznamN[0]**2 <= SeznamN[-1]: #Dokud bude ctverec prvniho prvku SeznamuN mensi nebo roven poslednimu
#prvku SeznamuN, vykonej:
Prvocisla.append(SeznamN[0]) # 1)K seznamu Prvocisla pripoj prvni cislo ze SeznamuN
Nasobky = range(SeznamN[0],SeznamN[-1]+1,SeznamN[0]) # 2)Vytvor seznam nasobku naposledy pripojeneho Prvocisla
for k in Nasobky: # 3)Pro kazde cislo "k" v seznamu Nasobky:
if k in SeznamN: # 1)Pouze pokud se k naleza v SeznamuN:
SeznamN.remove(k) # 1)Odstran cislo/nasobek k ze SeznamuN;kod se opakuje od 4 radku
#Prvni cislo v seznamu je vetsi jak odmocnina z cisla posledniho a tedy
Prvocisla.extend(SeznamN) #zbyla cisla jsou prvocisla. Extend je podobne k append.
print Prvocisla #Zobraz vysledek!
</source>
== Zdrojový kód v jazyce PHP ==
<source lang="php">
function erPrimes($max)
{
$numbers = range(2,$max,1); //inicializuji si pole cisel od 2 do $max po jedne
$primes = array(); // inicializace vystupniho pole
while (list($key,$value) = each($numbers)) { // nactu si dalsi cislo z pole
if ($value) { // zjistim jestli cislo uz neni vynulovane
for ($i=1;($exp = $value*$i) < $max;$i++) { // vynuluju vsechny nasobky aktualniho cisla
$numbers[$exp-2] = null; /* ///Opraveno/// U $exp musí být -2,
/ protože bychom při testování trojky
/ odebrali pětku - pole $numbers totiž vypadá takto:
/ Array ( [0] => 2 [1] => 3 [2] => 4 [3] => 5 ... [97] => 99 [98] => 100 )
/ Jak jste si mohli všimnout číslo 5 má index 3 a číslo 3 má index 1,
/ a zde nastává problém, kdybychom neodečetli od indexu dvojku, tak namísto
/ to, abychom vynulovali všechny násobky daného čísla, tak nulujeme nasobky
/ daného čísla zvětšeného o 2. Příklad:
/ Testujeme č. 3: Vynásobíme jedničkou, dostaneme trojku,
/ ale podle původního kódu bychom vymazali pětku,
/ protože proměnná $numbers s indexem 3 odkazuje na 5,
/ a proto musíme kód ošetřit tak,
/ aby index odkazoval na správné číslo, tzn. chceme vymazat trojku,
/ takže chceme aby proměnná $numbers s indexem 3 vymazala trojku.
/ Takže když na trojku odkazuje $numbers s indexem 1, tak musíme zařídit,
/ aby se index 1 opravdu rovnal, a proto je tam ta -2.
/ Číslo 3 je pouhý příklad, toto by nastalo u všech dalších čísel.
*/
}
$primes[] = $value; // pridam si zjistene prvocislo do vystupu
}
}
return $primes;
}
</source>
== Zdrojový kód v jazyce C# ==
<source lang="csharp">
int[] SieveOfEratosthenes(int max)
{
bool[] primesPredicate = new bool[++max].Select(x => x = true).ToArray();
for (int i = 2; i <= (int)Math.Sqrt(max); i++)
if (primesPredicate[i])
for (int j = i * 2; j < max; j += i)
primesPredicate[j] = false;
int index = 0;
return primesPredicate.Select(x => new { index = index++, primeP = x }).Where(x => x.primeP && x.index > 1).Select(x => x.index).ToArray();
}
</source>
== Zdrojový kód v jazyce Perl ==
<source lang="perl">
use warnings;
use strict;
print "Zadej N: ";
my $n = <STDIN>;
my @primes = (); # pole se stavy prvocisel (0-neni, 1-je prvocislo)
for (0..$n) {
push(@primes, 1); # povazuj vsechna cisla za prvocisla
}
# vyfiltruj prvocisla Eratosthenovym sitem
for my $i (2..int(sqrt($n))) {
if ($primes[$i]) {
for (my $j = $i * 2; $j <= $n; $j += $i) {
$primes[$j] = 0;
}
}
}
# vytiskni prvocisla od 2 do N
for my $i (2..$n) {
if ($primes[$i]) {
print $i . " ";
}
}
print "\n";
</source>
== Zdrojový kód v jazyce Haskell ==
<source lang="Haskell">
prvocisla n = sito [2..n]
where sito [] = []
sito (p:ms) = p:sito [m | m<-ms, m `mod` p /= 0]
</source>
== Zdrojový kód v jazyce Scala ==
<source lang="scala">
def EratosthenovoSito(max: Int): List[Int] = {
val min = 2
def jeDelitelne(a: Int, b: Int) = a % b == 0
def sito(cisla: List[Int], prvocisla: List[Int]): List[Int] = cisla match {
case cislo :: zbytek => sito(zbytek filterNot { jeDelitelne(_,cislo) },cislo :: prvocisla)
case Nil => prvocisla.reverse
}
sito((min to max).toList, List[Int]())
}
</source>
== Externí odkazy ==
| |||