Ověřovač prvčísel

Prvočísla mají přesně dva dělitele: 1 a sama sebe.

První prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Prvočísla jsou stavebními kameny všech celých čísel.

Každé celé číslo > 1 lze jedinečně vyjádřit jako součin prvočísel.

Například 60 = 2² × 3 × 5.

To je zásadní v matematice a v kryptoanalýze.

Chcete-li ověřit, zda je číslo n prvočíslo, otestujte, zda ho rovnoměrně dělí nějaké celé číslo mezi 2 a odmocninou z n; pokud žádné takové neexistuje, n je prvočíslo.

Nejprve vyřešte malé případy:

• čísla menší než 2 nejsou prvočísla
• 2 a 3 jsou prvočísla
• každé sudé číslo větší než 2 je složené

Poté otestujte liché dělitele až do √n, protože dělitelé chodí vždy v párech, jejichž menší člen nemůže překročit odmocninu.

Například kontrola čísla 97 vyžaduje otestování pouze čísel 3, 5 a 7 (protože √97 ≈ 9,85) a žádné z nich ho nedělí, takže 97 je prvočíslo. Wolfram MathWorld popisuje tuto metodu jako zkušební dělení, což je nejdirectnější test primality.

Metoda odmocniny znamená, že stačí testovat potenciální dělitele pouze do výše √n namísto celé cesty až do n.

Důvodem je, že pokud n = a × b, pak alespoň jeden z činitelů a nebo b musí být menší nebo roven √n; jinak by jejich součin přesáhl n. Pokud tedy pod √n nenajdete žádného činitele, neexistuje ani žádný větší.

Tento postup dramaticky snižuje množství práce: ověření, zda je 9 973 prvočíslo, vyžaduje testování dělitelů pouze do zhruba 99, nikoli téměř do 10 000.

Khan Academy využívá tuto argumentaci s páry k vysvětlení, proč zkušební dělení končí u odmocniny, díky čemuž je ruční ověřování prvočísel praktické.

Eratosthenovo síto nachází všechna prvočísla do určitého limitu N tím, že opakovaně označuje násobky každého prvočísla jako složená čísla.

Začněte se seznamem celých čísel od 2 do N. Vezměte 2, oznamte 4, 6, 8, ... jako složená; přejděte k dalšímu neoznačenému číslu, 3, a označte 6, 9, 12, ...; pokračujte s 5, 7 a tak dále. Čísla, která zůstanou neoznačená, jsou prvočísla.

Při použití do 30 zanechá síto čísla 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Tento algoritmus (popsaný v encyklopedii Britannica), pojmenovaný po řeckém matematikovi Eratosthenovi z Kyrény, je jedním z nejstarších a nejefektivnějších způsobů, jak vypsat prvočísla v daném rozsahu.

Základní věta aritmetiky říká, že každé celé číslo větší než 1 je buď prvočíslem, nebo ho lze zapsat jako součin prvočísel přesně jedním způsobem, nepočítáme-li pořadí činitelů.

Například 360 = 2³ × 3² × 5 a žádná jiná kombinace prvočísel nedá po vynásobení 360. Právě tato jedinečnost je důvodem, proč se prvočísla nazývají stavebními kameny celých čísel.

Podle serveru Wolfram MathWorld tato věta tvoří základ prvočíselného rozkladu, výpočtu největšího společného dělitele a modulární aritmetiky.

Naše kalkulačka ji využívá při rozkladu čísla na součin, což zaručuje, že vrácený prvočíselný rozklad je jediný možný.

Dvojčata prvočísel (též prvočíselná dvojčata) jsou dvojice prvočísel, jejichž rozdíl je přesně 2, například (3, 5), (5, 7), (11, 13), (17, 19) a (29, 31).

Mezera mezi následujícími po sobě jdoucími prvočísly obecně roste s tím, jak se čísla zvětšují, přesto se dvojčata objevují dál. Zda existuje nekonečně mnoho prvočíselných dvojčat, je slavná domněnka o prvočíselných dvojčatech, která dosud nebyla dokázána.

On-Line Encyclopedia of Integer Sequences (OEIS) katalogizuje menší členy dvojic prvočíselných dvojčat pod sekvencí A001359.

Pochopení mezer mezi prvočísly pomáhá vysvětlit, proč jsou prvočísla řidší: poblíž jednoho milionu jsou prvočísla od sebe v průměru vzdálena zhruba 14, což je trend popsaný prvočíselnou větou v digitální knihovně matematických funkcí NIST.

Prvočísla pohánějí moderní kryptografii, zejména šifrování RSA, které zabezpečuje online bankovnictví, weby s HTTPS a digitální podpisy. RSA spoléhá na fakt, že vynásobení dvou velkých prvočísel je snadné, ale zpětné rozložení součinu na tato prvočísla je výpočetně obtížné.

Kromě zabezpečení se prvočísla objevují zde:

• při určování velikosti hashovacích tabulek (tabulky o prvočíselné délce omezují kolize)
• při generování pseudonáhodných čísel
• v kusech opravujících chyby
• v životních cyklech cikád, které se vyvinuly tak, aby odpovídaly letům s prvočíselnou hodnotou, čímž se vyhýbají predátorům

Britannica poznamenává, že prvočíselný rozklad také zjednodušuje zlomky a počítá nejmenší společné násobky. Naše kalkulačka tyto úkoly podporuje rozkladem čísel a generováním prvočísel pro návrh algoritmů i domácí úkoly z matematiky.

Prvočíslo má přesně dva různé kladné dělitele, 1 a samo sebe, zatímco složené číslo má dělitelů více než dva.

Například 13 je prvočíslo (dělitelé 1 a 13) a 12 je složené číslo (dělitelé 1, 2, 3, 4, 6, 12). Číslo 1 není ani prvočíslem, ani číslem složeným, protože má pouze jednoho dělitele.

Tato konvence udržuje základní větu aritmetiky čistou: kdyby se 1 počítala jako prvočíslo, rozklady na součinitele by již nebyly jedinečné, protože byste mohli vložit libovolný počet jedniček.

Encyclopaedia Britannica i Khan Academy tento rozdíl zdůrazňují, a proto náš nástroj označuje jedničku odděleně od prvočísel a složených čísel.

Mersennova prvočísla jsou prvočísla ve tvaru 2^p − 1, kde exponent p je sám o sobě prvočíslem; příklady zahrnují 3 (2² − 1), 7 (2³ − 1), 31 (2⁵ − 1) a 127 (2⁷ − 1).

Ne každý prvočíselný exponent však vede k prvočíslu: 2¹¹ − 1 = 2047 = 23 × 89 je složené číslo.

Mersennova prvočísla jsou důležitá proto, že díky rychlému testu zvanému Lucas-Lehmerův test se ověřují snáze než libovolná čísla, takže největší známá prvočísla jsou téměř vždy Mersennova prvočísla o desítkách milionů cifer.

Projekt Great Internet Mersenne Prime Search (GIMPS) koordinuje dobrovolníky při jejich objevování. Sekvence OEIS A000668 uvádí známá Mersennova prvočísla.

• Nejčastější chybou je považovat 1 za prvočíslo; není tomu tak, protože prvočíslo musí mít přesně dva dělitele.
• Další chybou je zapomenout, že 2 je jediné sudé prvočíslo, takže ho lidé neoprávněně vynechávají nebo se nesprávně domnívají, že jiná sudá čísla mohou být prvočísly.
• Třetí chybou je ukončení zkušebního dělení příliš brzy nebo příliš pozdě: musíte otestovat všechny dělitele až do √n, nejen několik malých.
• Lidé si také pletou prvočíselný rozklad s výpisem všech dělitelů; číslo 12 má dělitele 1, 2, 3, 4, 6, 12, ale prvočíselný rozklad pouze 2² × 3.
• Nakonec, předpokládat, že každé číslo ve tvaru 6k ± 1 je prvočíslo, je nepravdivé; 25 = 6(4) + 1 je složené číslo.