Prvočísla jsou čísla, která se dělí beze zbytku pouze na sebe a na jednotku. Jsou základem pro mnoho matematických a algoritmických operací. Při programování v JavaScriptu je také často nutné zkontrolovat, zda je číslo jednoduché nebo ne.
Existuje několik způsobů, jak zkontrolovat čísla pro jednoduchost v JavaScriptu. Jednou z nejjednodušších a nejúčinnějších metod je použití algoritmu pro kontrolu čísla na dělitelnost všech čísel od 2 do n / 2, kde n je číslo, které je třeba zkontrolovat.
Dalším způsobem, jak ověřit čísla pro jednoduchost, je použití eratosférické mřížky. Je to algoritmus, který vám umožňuje najít všechna prvočísla před daným číslem n. v podstatě se skládá z po sobě jdoucích kroků: nejprve se vytvoří seznam všech čísel od 2 do n, poté se odstraní všechna čísla, která se dělí na již nalezená prvočísla.
Co jsou prvočísla?
Prvočísla jsou například čísla 2, 3, 5, 7, 11 atd. Na rozdíl od prvočísel mají složená čísla více než dva dělitele.
Prvočísla jsou důležitá v matematice a široce se používají v kryptografii a dalších oblastech. Používají se například k vytváření šifer, generování náhodných čísel, faktorizaci čísel a kontrole čísel pro jednoduchost.
Ověření čísla pro jednoduchost může být užitečné v algoritmech, programování a při řešení problémů souvisejících s čísly.
Definice a vlastnosti prvočísel
Vlastnosti prvočísel:
- Prvočíslo je vždy přirozené číslo větší než 1.
- Prvočísla nemají žádné dělitele kromě 1 a sebe sama.
- Prvočísla nemohou být kladná nebo záporná čísla nebo desetinná čísla.
- Množina všech prvočísel je nekonečná a nelze je zcela vyjmenovat.
- Největším prvočíslem je číslo 2.
- Jednotka není prvočíslo, protože má pouze jeden dělitel.
Definice prvočísel hraje důležitou roli, například v kryptografii, při vytváření šifer a generování náhodných čísel.
Algoritmy pro testování jednoduchosti
Existuje několik ověřovacích algoritmů pro jednoduchost čísla. Zde jsou dva z nejběžnějších:
| Metoda přebírání dělitelů | Metoda eratosfénové mřížky |
| Tato metoda je založena na překročení všech možných dělitelů čísla od 2. Pokud číslo nelze sdílet beze zbytku alespoň na jedno číslo, je to jednoduché. Je zřejmé, že tato metoda není optimální pro velká čísla, protože vyžaduje mnoho výpočetních zdrojů. | Metoda eratosfénové mřížky je založena na principu vyloučení. Nejprve se vytvoří pole od 2 do samotného čísla, které je třeba zkontrolovat. Poté počínaje 2 jde po poli a vyškrtne všechna čísla, která jsou jeho násobky. Pak se přesune do dalšího neveřejného čísla a pokračuje v podobných operacích. Po dokončení algoritmu jsou všechna čísla, která zůstala vyškrtnuta, jednoduchá. |
Použijte jeden z těchto algoritmů k ověření čísel pro jednoduchost v JavaScriptu a vyberte nejvhodnější pro vaše úkoly.
Linear Sieve: efektivní ověřovací algoritmus pro jednoduchost
Algoritmus lineární mřížky se skládá z následujících kroků:
- Vytvoření pole z n prvků, kde n je největší číslo, které je třeba otestovat na jednoduchost. Na začátku jsou všechny prvky pole označeny jako prvočísla.
- Pro každé číslo p od 2 do √n postupujte takto:
- Pokud je p označeno jako prvočíslo, označte každé číslo, které je jeho násobkem, jako složené číslo.
Algoritmus lineární mřížky výrazně urychluje kontrolu jednoduchosti čísel, zvláště když jsou čísla dostatečně velká. Namísto přepočítání všech čísel na dané, algoritmus najít všechna prvočísla na dané číslo jejich označením.
Použití algoritmu lineární mřížky může být užitečné pro různé úkoly, které vyžadují ověření jednoduchosti velkého počtu čísel.
Testy jednoduchosti pro velká čísla
Jedním z nejúčinnějších algoritmů pro testování jednoduchosti velkých čísel je algoritmus Miller-Rabin. Je založen na Fermatově testu a testuje čísla na jednoduchost pomocí náhodných čísel.
Millerův-Rabinův algoritmus funguje následovně:
- Je vybrána náhodná základna a, která by měla být menší než kontrolované číslo n.
- Hodnoty r A s jsou vypočítány tak, že n-1 = 2^s * r, kde r je liché číslo.
- Vypočítá se hodnota x = a^R mod n.
- Pokud se X rovná 1 nebo -1 (mod n), pak je číslo n s největší pravděpodobností prvočíslo.
- Pokud se X rovná 1 nebo -1(mod n), pak se provádí r-1 operace vztyčení na druhou, dokud není dosaženo hodnoty x = a^(2^i * r) mod n pro určité i od 0 do s-1.
- Pokud je poslední hodnota x -1 (mod n), pak je číslo n s největší pravděpodobností prvočíslo.
- Pokud poslední hodnota x Není 1 nebo -1 (mod n), pak je číslo n přesně složené.
Millerův-Rabinův algoritmus umožňuje ověřit jednoduchost čísla s libovolným nastaveným stupněm jistoty. Čím větší je počet opakování algoritmu pro každou kontrolu, tím menší je pravděpodobnost falešně pozitivních výsledků. Zvýšení počtu opakování však také zvyšuje náklady na výpočetní zdroje.
K ověření jednoduchosti velkých čísel v JavaScriptu lze použít hotové knihovny, jako je BigInteger.js nebo crypto-random-number. Poskytují funkce pro provádění Millerova-Rabinova algoritmu a dalších testů jednoduchosti.
Příklad použití funkce ověření jednoduchosti čísla pomocí knihovny BigInteger.js:
const BigInteger = require('big-integer');function isPrime(number) const num = '1234567890123456789012345678901234567890';Je důležité vzít v úvahu, že kontrola jednoduchosti velkých čísel může být časová operace, zejména pro čísla s velkým počtem číslic. Před provedením kontroly byste proto měli pečlivě vyhodnotit možnou dobu provádění a v případě potřeby ji omezit.
Implementace kontroly prvočísel v JavaScriptu
Jedním z nejúčinnějších přístupů k ověření čísla pro jednoduchost je použití algoritmu Eratosthen. Tento algoritmus umožňuje najít všechna prvočísla v určitém rozsahu.
V JavaScriptu lze implementovat ověření čísla pro jednoduchost pomocí funkce, která přijme číslo jako argument a vrátí bulovou hodnotu - true, pokud je číslo prvočíslo, a false, pokud číslo není prvočíslo.
Zde je jedna z možností implementace:
function isPrime(number) for (let i = 2; i >return true;>V této implementaci funkce kontroluje, zda je číslo menší nebo rovné 1. Pokud je číslo takové, není jednoduché a funkce vrací false. Funkce poté přeruší všechna čísla od 2 do druhé odmocniny z čísla a zkontroluje, zda je číslo beze zbytku dělitelné žádným z těchto čísel. Pokud je dělitelné, číslo není jednoduché. Pokud žádné z čísel nerozdělí číslo beze zbytku, pak je číslo prvočíslo a funkce vrátí true.
Pomocí této funkce můžete ve svém JavaScript kódu zkontrolovat čísla pro jednoduchost.
Příklady použití funkce ověřování prvočísel
Zde je několik příkladů použití funkce kontroly prvočísel:
- Kontrola čísla 7 pro jednoduchost:
- isPrime(7); // true
- Kontrola čísla 15 pro jednoduchost:
- isPrime(15); // false
- Kontrola čísla 23 pro jednoduchost:
- isPrime(23); // true
K ověření prvočísel v daném rozsahu můžete také použít cyklus a funkci:
function printPrimes(start, end) >>printPrimes(1, 50); // Выведет все простые числа от 1 до 50Můžete tedy použít funkci kontroly prvočísel k ověření konkrétního čísla pro jednoduchost nebo odvodit všechna prvočísla v daném rozsahu.