Vypište prvočísla
Celé číslo větší než 1 se nazývá prvočíslo, jestliže není dělitelné beze zbytku jiným celým číslem než 1 a sebou samým.
Jinými slovy, číslo n > 1 je prvočíslo, jestliže není dělitelné beze zbytku jiným číslem než 1 a n.
Například 5 je prvočíslo, protože není dělitelné beze zbytku číslem 2, 3 ani 4.
Napište kód, který vypíše všechna prvočísla v intervalu od 2 do n.
Například pro n = 10 bude výsledek 2,3,5,7.
P.S. Kód by měl fungovat pro jakékoli n. Neměl by být vyladěn jen pro nějakou pevnou hodnotu.
Pro tuto úlohu existuje mnoho algoritmů.
Použijeme vnořený cyklus:
pro každé i v intervalu {
ověř, zda i má dělitele mezi 1..i
pokud ano => i není prvočíslo
pokud ne => i je prvočíslo, zobraz ho
}Kód s použitím návěští:
let n = 10;
dalšíPrvočíslo:
for (let i = 2; i <= n; i++) { // pro každé i...
for (let j = 2; j < i; j++) { // hledáme dělitele...
if (i % j == 0) continue dalšíPrvočíslo; // není to prvočíslo, přejdeme k dalšímu i
}
alert( i ); // je to prvočíslo
}Je zde mnoho prostoru k optimalizaci. Můžeme se například dívat jen na dělitele od 2 do odmocniny i. Kdybychom však chtěli být opravdu efektivní i pro velké intervaly, museli bychom změnit přístup a zaměřit se na vysokou matematiku a složité algoritmy, např. kvadratické síto, Obecné číselné teoretické síto (GNFS) atd.