Jak zjistit, zda je zadané číslo prvočíslem?

Co je to vlastně prvočíslo? Je to číslo, které je dělitelné pouze jedničkou nebo sebou samým.

1. verze

Z definice vyplývá, že nejjednodušší je zkusit vydělit zadané číslo všemi čísly od 2 do čísla o jedničku menší než zadané a jestli nebude žádným z nich bezezbytku dělitelné, tak je to prvočíslo.

Funkce by mohla vypadat asi takto:

function jePrvocislo(cislo) {   for (var i = 2; i < cislo; i++)     if (cislo % i == 0)       return (false);   return (true); }

Toto řešení je funkčně správné, ale má jednu obrovskou nevýhodu. Je velmi neefektivní a i na rychlém počítačí trvá výpočet pro velká čísla dlouho. Nejhorším případem je velké prvočíslo.

2. verze

Co by se dalo zlepšit? Možností je několik. Začneme třeba tím, že si uvědomíme, že pokud číslo není dělitelné dvojkou (a není přesně 2), tak můžeme vynechat všechny sudé dělitele.

Upravená funkce:

function jePrvocislo2(cislo) {   if ((cislo != 2) && (cislo % 2 == 0))     return (false);   for (var i = 3; i < cislo; i = i + 2)     if (cislo % i == 0)       return (false);   return (true); }

Touto úpravou zmenšíme množinu možných dělitelů i čas pro zjištění na polovinu.

3. verze

Co by se dalo ješte upravit? Například všechna čísla končící číslicí 5 jsou vždy dělitelná pěti. Úvaha je to dobrá, ale na to přijde cyklus už v druhém průchodu, takže nic neušetříme. Ani pravidlo, že když je součet číslic dělitelný třemi, tak je i dané číslo dělitelné třemi nám nepomůže.

Lepší je jiná myšlenka. Musíme procházet všechna čísla až do čísla o jedničku menšího? Pokud je číslo dělitelné, tak má vždy dělitele dva. Nám stačí najít toho menšího. Hledáme tedy dělitele pouze do té doby, dokud je první dělitel menší. Stejné dělitele získáme odmocninou, můžeme tedy hranici pro hledaní vypočítat jako celé číslo z druhé odmocniny zadaného čísla.

Příklad pro lepší pochopení:
Máme číslo 29. Celé číslo z druhé odmocniny je 5. Hledám tedy dělitele pouze do čísla 5, protože při děliteli větším by byl celočíselný výsledek menší než 5 a na ten bych už přišel dříve. Stačí tedy zkusit čísla 2, 3 a 5. Nedělí ho ani jedno, tak je to prvočíslo.

Upravená funkce:

function jePrvocislo3(cislo) {   if ((cislo != 2) && (cislo % 2 == 0))     return (false);   var hranice = Math.floor(Math.sqrt(cislo));   for (var i = 3; i < hranice; i = i + 2)     if (cislo % i == 0)       return (false);   return (true); }

Tato úprava velmi výrazně zmenšuje množinu možných dělitelů. Např. pro prvočíslo 100 003 musí první funkce otestovat 100 001, druhá funkce 50 001 a třetí funkce jen 159 čísel.

---

Zde si můžete vyzkoušet rychlost uvedených funkcí

Testované číslo:
Je to prvočíslo?
Doba zjišťování:	ms

Přidávám tabulku časů (v ms) pro vybraná prvočísla na počítači s procesorem Pentium 4 2,8GHz.

Funkce\číslo	101	100 003	1 000 003	10 000 019
jePrvočíslo	0	109	1079	11 375
jePrvočíslo2	0	63	656	6 750
jePrvočíslo3	0	0	0	0