algoritmus denně: jak zkontrolovat prvočíslo v JavaScriptu

Marina Šemešová
Marina Shemesh

sledovat

28. května 2020 * 7 min čtení

je téměř zaručeno, že v určitém okamžiku ve vašem kódování vzdělání budete vyzváni k napsání nějaký typ funkce, která zahrnuje prvočísla. Je to populární cvičení v kódování boot tábory a někdy dokonce pop – up v pracovních pohovorech.

co jsou prvočísla?

prvočíslo je přirozené číslo větší než 1, jehož jedinými faktory jsou 1 a samotné číslo. To znamená, že může být děleno rovným dílem 1 a samo.

přirozená čísla jsou kladná celá čísla, jako je 1, 5, 201, 229999 atd. Číslo 0, zlomky, desetinná místa a záporná čísla nejsou přirozená čísla.

číslo 5 je prvočíslo, protože jeho jedinými faktory jsou 1 a 5. Neexistuje žádný jiný způsob ,jak „vytvořit“ číslo 5.

číslo 4 není prvočíslo, protože 2 x 2 nám také dává 4.

číslo 20 není prvočíslo, protože 5 x 4 nám také dává 20, stejně jako 2 x 10.

prvočísla nejsou nikdy sudá (s výjimkou 2)

jedním z nejrychlejších způsobů, jak zkontrolovat, zda je číslo prvočíslem nebo ne, je zkontrolovat, zda se jedná o sudé číslo. Pokud lze číslo dělit 2 bez zanechání zbytku, již nesplňuje definici prvočísla-číslo, které lze dělit rovným dílem 1 a samo o sobě.

v JavaScriptu můžeme zkontrolovat sudá čísla pomocí operátora modulo (%).

operátor modulo vrátí zbytek poté, co je jedno celé číslo děleno jiným.
například 12% 5 vrací 2.
a 59 % 5 vrací 4.

pokud vydělíte celé číslo 2 a zbytek je 0, víme, že celé číslo je sudé číslo.

například 10 % 2 = 0
a 2200 % 2 = 0

v JavaScriptu to bude vypadat takto:
počet % 2 === 0

začněme tedy vytvářet naši funkci JavaScript, abychom zkontrolovali, zda je číslo prvočíslo nebo ne:

function isPrime(num) {
if (num % 2 === 0) { return false;
} return true;}
//isPrime(40) gives us a False answer
//isPrime(101) gives us a True answer

pamatujte, že 2 je prvočíslo

výše uvedená funkce však také uvádí, že 2 není prvočíslo, takže budeme muset přepsat naši funkci. Můžeme se také postarat o jakákoli jiná celá čísla, která nejsou celá čísla, jako je 0 a záporná čísla.

function isPrime(num) {
if (num === 2) return true;
if (num <= 1) return false; if (num % 2 === 0) {
return false;
}
return true;
}//isPrime(0.5) gives us a False answer
//isPrime(2) gives us a True answer
//isPrime(577) gives us a True answer

Klíčové slovo „návrat“ signalizuje ukončení funkce, když narazí na příkaz, který je pravdivý. Pokud je číslo 2, funkce přestane běžet na druhém řádku:

if (num === 2) return true;

zde najdete velký seznam známých prvočísel, které vám pomohou zkontrolovat funkci.
ne všechna nerovnoměrná čísla jsou prvočísla

Tato funkce funguje dobře pro kontrolu, zda je číslo sudé nebo ne, ale selže s nerovnoměrnými čísly, jako jsou 9 a 27, které nejsou prvočísla.

budeme muset zkontrolovat, zda lze parametr rozdělit na jiné faktory (s výjimkou 1, samotného a 2), aniž bychom zanechali zbytek. Například číslo 9 může být také děleno 3.

děláme to tak, že použijeme smyčku for, kde při každé iteraci je parametr dělen jinou proměnnou smyčky. Smyčka běží, dokud nejsou k dispozici žádné zbytky nebo nejsou k dispozici žádné další proměnné smyčky.

function isPrime(num) {
if (num <= 1) return false;
if (num === 2) return true; for (let i= 2; i < num; i++) { //we start with 2 to weed out the even numbers if (num % i === 0) {
return false;
}
} return true;
}//isPrime(9) is False
//isPrime(11) is True
//isPrime(27) is False

funkce udržuje opakování a kontrolu zbytků. Při každé iteraci je argument rozdělen novou proměnnou smyčky a zbytek je zkontrolován. Pokud je zbytek 0, znamená to, že argument je zcela dělitelný jiným číslem než sám a není prvočíslem.

boční poznámka: Jaký je rozdíl mezi parametrem a argumentem?
parametry jsou proměnné používané jako součást definice funkce. Například num ve funkci isPrime(num) je parametr.

argumenty jsou hodnoty předané funkci při jejím vyvolání. Například
číslo 9 v isPrime(9) je argument.

pokud je zbytek, funkce se znovu iteruje, dokud nedosáhne limitu

 i < num

když je dosaženo konečné iterace a zbývá ještě zbytek, argument je prvočíslo a funkce se zastaví.
končíme smyčkovou proměnnou, která je o jedno číslo menší než parametr, protože nás nezajímají faktory, které jsou větší než argument.

rychlá demonstrace

ukážeme to prvočíslem 5.

function isPrime(num) {
if (num <= 1) return false;
//5 is larger than 1, so we continue with the function if (num === 2) return true;
//5 is not 2, so we continue with the function for (let i= 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;}

první smyčka:
1. i = 2 a 2 < 5, takže pokračujeme smyčkou
2. 5 % 2 dává zbytek, takže neopustíme smyčku, ale pokračujeme i++

druhá smyčka:
1. i = 3 a 3 < 5, takže pokračujeme smyčkou
2. 5 % 3 dává zbytek, takže neopustíme smyčku, ale pokračujeme i++

třetí smyčka:
1. i = 4 a 4 < 5 a dosáhli jsme konce smyčky, protože 5 není < než 5
2. 5 % 4 dává zbytek. To znamená, že číslo 5 je prvočíslo

pomocí odmocnin s většími prvočísly

prvočísla rychle eskalují do obrovských čísel. To znamená, že naše smyčka for neustále opakuje z proměnné one loop do další mnohokrát.

proces můžeme zkrátit pomocí druhé odmocniny parametru. Druhá odmocnina celého čísla je číslo, které bylo vynásobeno samo o sobě, aby se vytvořil produkt.

druhá odmocnina z 81 je 9, protože 9 x 9 = 81.

namísto iterace od 2 do 80, abychom zkontrolovali, zda zbývají nějaké zbytky nebo ne, můžeme iterovat až do 9 včetně druhé odmocniny 81.
9% 9 = 0, což znamená, že 81 není prvočíslo.
to dává smysl, protože 9 x 9 jsou faktory 81, což znamená, že to není v souladu s definicí prvočísla-číslo, které může být děleno rovným dílem samo o sobě a 1.

v JavaScriptu najdete druhou odmocninu čísla pomocí matematiky.náměstí. Píšeme to takto:

Math.sqrt(num);

použijme ji v naší funkci, která kontroluje, zda je číslo prvočíslo:

function isPrime(num) {
if (num <= 1) return false;
if (num=== 2) return true; let num2 = Math.sqrt(num);//num2 is the square root of num for (let i= 2; i <= num2; i++) { //note that we are working now with the square root if (num2 % i === 0) { return false;
}
}
return true; }isPrime(521) //is True
isPrime(9801) //is False
isPrime(13037) //is True

proč jsou prvočísla tak užitečná?

v kontaktu, sci-fi kniha Carl Sagan, cizinci poslat dlouhý řetězec prvočísel jako důkaz, že jejich zpráva je z inteligentní životní síly. Nekomunikujeme (zatím) s mimozemšťany prostřednictvím prvočísel, ale využíváme je různými způsoby právě tady na planetě Zemi.

cikády se objevují v synchronizaci v přesných prvočíselných cyklech. Nepravidelné cykly znamenají, že se z tohoto hmyzu nevyvinuli žádní predátoři. Také skutečnost, že se všichni vynoří ze země, zvyšuje šanci jednotlivce na přežití.

obrazovky používají prvočísla k definování intenzity barev pixelů. Používají se také při výrobě nástrojů, aby se zbavili harmonií. Dvě ozubená kola, která sdílejí násobek, budou znovu a znovu zabírat stejné zuby, což vede k nerovnoměrnému opotřebení. Ozubená kola, která mají na svých zubech prvočíselný počet zubů, vydrží déle.

prvočísla jsou však většinou v moderní počítačové bezpečnosti. Není to tak těžké najít velká prvočísla, ale je velmi obtížné započítat velká čísla do prvočísel.

je snadné zjistit, že 27 je 3 x 3 x 3, ale je mnohem obtížnější zjistit, že 2 244 354 je 2 x 3 x 7 x 53,437. A 2 244 354 není ani tak velké číslo. Nalezení hlavních faktorů je technicky otázkou času, ale protože to bude trvat tak dlouho, říkáme, že to nelze udělat.

moderní šifrovací algoritmy využívají skutečnosti, že zatím neexistuje žádný počítač, který by mohl vzít super velké číslo a rychle zjistit, které prvočísla se do něj dostaly.

můžete nakupovat online nebo posílat šifrovanou zprávu prostřednictvím aplikace v telefonu, ale někde vám nějak prvočísla pomáhají udržovat vaše tajemství v bezpečí.

zde jsou další tři odkazy na další články „algoritmus denně“:

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.